Submission #3426658

---

Source Code Expand

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
using Int = long long;
int main()
{
    Int N, C;
    cin >> N >> C;
    vector<Int> X(N+1), V(N+1);
    for (int i = 1; i <= N; i++) cin >> X[i] >> V[i];
    vector<Int> cw(N+1), ccw(N+1);
    vector<bool> cwb(N+1), ccwb(N+1);
    for (int i = 1; i <= N; i++) {
        cw[i] = cw[i-1] + V[i];
        ccw[i] = ccw[i-1] + V[N+1-i];
    }
    Int bestcw = 0, bestccw = 0;
    for (int i = 1; i <= N; i++) {
        Int s = cw[i] - X[i];
        if (s > bestcw) {
            bestcw = s;
            cwb[i] = true;
        }
    }
    for (int i = 1; i <= N; i++) {
        Int s = ccw[i] - (C - X[N+1-i]);
        if (s > bestccw) {
            bestccw = s;
            ccwb[i] = true;
        }
    }
    Int result = max(bestcw, bestccw);
    Int j;
    j = N;
    for (int i = 1; i <= N - 1; i++) {
        j = min(j, N - i);
        while (j > 0 && !ccwb[j]) j--;
        result = max(result, cw[i] - 2*X[i] + ccw[j] - (C - X[N+1-j]));
    }
    j = N;
    for (int i = 1; i <= N - 1; i++) {
        j = min(j, N - i);
        while (j > 0 && !cwb[j]) j--;
        result = max(result, ccw[i] - 2*(C - X[N+1-i]) + cw[j] - X[j]);
    }
    cout << result << endl;
    return 0;
}

Submission Info

Judge Result