Submission #20121427

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main()
{
  ll n, c;
  cin >> n >> c;
  vector<ll> x(n);
  vector<ll> v(n);
  for (int i = 0; i < n; i++){
    cin >> x[i] >> v[i];
  }

  // d[i] : v の累積和
  vector<ll> d(n);
  d[0] = v[0];
  for (int i = 1; i < n; i++){
    d[i] = d[i-1] + v[i];
  }

  // O - xi 時計まわりケースでの最大値
  // 初期値は O-O （なにもせず退店）
  vector<ll> g(n);
  vector<ll> z(n);
  if (d[0]-x[0] > 0){
    g[0] = d[0]-x[0];
    z[0] = x[0];
  } else {
    g[0] = 0;
    z[0] = 0;
  }
  for (int i = 1; i < n; i++){
    ll fi = d[i] - x[i];
    if (fi > g[i-1]){
      g[i] = fi;
      z[i] = x[i];
    } else {
      g[i] = g[i-1];
      z[i] = z[i-1];
    }
  }

  ll ans = g[n-1];
  ans = max(ans, d[n-1] - (c - x[0]));

  // O-A-B または O-B-A (B: xi)
  for (int i = 0; i < n-1; i++){
    ll gainR = d[n-1] - d[i] - (c - x[i+1]);
    ans = max(ans, gainR);
    ll gainL = g[i];
    ans = max(ans, gainL + gainR - z[i]);
    ans = max(ans, gainL + gainR - (c - x[i+1]));
  }

  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result