Submission #4050106

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll X[100010], Y[100010];
ll turnR[100010], turnL[100010];

int main() {
  ll N, C;
  cin >> N >> C;
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }

  ll sum = 0, maxv = 0;
  for(int i = 0; i < N; i++) {
    sum += Y[i];
    maxv = max(maxv, sum - X[i]);
    turnL[i] = maxv;
  }

  sum = 0, maxv = 0;
  for(int i = N -1; i >= 0; i--) {
    sum += Y[i];
    maxv = max(maxv, sum - X[i]);
    turnR[i] = maxv;
  }

  ll ans = 0;
  for (int i = 0; i < N; i++) {
    ll tmp = turnL[i];
    if (i < N -1) {
      tmp += max(0LL, turnR[i + 1] - X[i]);
      ans = max(ans, tmp);
    }
  }
  for (int i = N -1; i >= 0; i--) {
    ll tmp = turnR[i];
    if (i) {
      tmp += max(0LL, turnL[i - 1] - (C- X[i]));
      ans = max(ans, tmp);
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result