Submission #2544646

---

Source Code Expand

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <limits>
#include <cmath>
#include <numeric>
#include <string>

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
#define rep(i, a, b) for(int i = (a); i < (b); ++i )
#define rrep(i, a, b) for(int i = (a); i > (b); --i )
#define REP(i, a, b) for(int i = (a); i <= (b); ++i )
#define RREP(i, a, b) for(int i = (a); i >= (b); --i )
#define llrep(i, a, b) for(ll i = (a); i < (b); ++i )
#define llrrep(i, a, b) for(ll i = (a); i > (b); --i )
#define llREP(i, a, b) for(ll i = (a); i <= (b); ++i )
#define llRREP(i, a, b) for(ll i = (a); i >= (b); --i )
#define ullrep(i, a, b) for(ull i = (a); i < (b); ++i )
#define ullrrep(i, a, b) for(ull i = (a); i > (b); --i )
#define ullREP(i, a, b) for(ull i = (a); i <= (b); ++i )
#define ullRREP(i, a, b) for(ull i = (a); i >= (b); --i )

vector<ll> X;
vector<ll> V;
vector<ll> S;
vector<ll> pmax;
vector<ll> nmax;
ll n;
ll c;
int main() {
    cin >> n >> c;
    X.resize(n+1, 0);
    V.resize(n+1, 0);
    S.resize(n+1, 0);
    pmax.resize(n+1, 0);
    nmax.resize(n+1, 0);
    llrep(i, 0, n) {
        cin >> X[i+1] >> V[i+1];
    }

    ll ans = 0;
    llrep(i, 0, n) {
        S[i+1] = S[i] + V[i+1];
        ans = max(ans, S[i+1]-X[i+1]);
    }

    llrep(i, 0, n) {
        if ((S[pmax[i]] - X[pmax[i]]) < (S[i+1] - X[i+1])) {
            pmax[i+1] = i + 1;
        }else{
            pmax[i+1] = pmax[i];
        };

        if ((S[nmax[i]] - 2 * X[nmax[i]]) < (S[i+1] - 2 * X[i+1])) {
            nmax[i+1] = i + 1;
        }else{
            nmax[i+1] = nmax[i];
        };
    }
    llrrep(i, n, 0) {
        ans = max(ans, S[pmax[i-1]] + (S[n] - S[i-1]) - (X[pmax[i-1]] + 2 * (c - X[i])));
        ans = max(ans, S[nmax[i-1]] + (S[n] - S[i-1]) - (X[nmax[i-1]] * 2 + (c - X[i])));
    }
    cout << ans << endl;
}

Submission Info

Judge Result