Submission #2393206


Source Code Expand

Copy
/* ---------- STL Libraries ---------- */

// IO library
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>

// container library
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>


/* ---------- Namespace ---------- */

using namespace std;


/* ---------- Type Abbreviation ---------- */

template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

using ll = long long;
using PL = P<ll, ll>;
using PS = P<string, ll>;

using VI = V<int>;
using VVI = V<VI>;
using VL = V<ll>;
using VVL = V<VL>;
using VS = V<string>;
using VB = V<bool>;
using VVB = V<VB>;
using VPL = V<PL>;
using VPS = V<PS>;

#define fst first
#define snd second


/* ---------- conversion ---------- */

#define INT(c) static_cast<int>(c)
#define CHAR(n) static_cast<char>(n)
#define LL(n) static_cast<ll>(n)


/* ---------- container ---------- */

#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define GSORT(c) sort(ALL(c), greater<decltype((c).front())>())
#define SZ(x) (LL((x).size()))


/* ---------- repetition ---------- */

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
#define RFOR(i, a, b) for (ll i = (a); i >= (b); i--)
#define RREP(i, n) RFOR(i, n, 0)
#define RNREP(i, n) RFOR(i, n, 1)

// Usual REP runs from 0 to n-1 (R: n to 0)
// Natural REP runs from 1 to n (R: n to 1)


/* ---------- Constants ---------- */

// const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const ll dx[4] = {0, -1, 1, 0};
// const ll dy[4] = {-1, 0, 0, 1};
// const ll dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const ll dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};


/* ---------- Debug ---------- */
#define GET_VAR_NAME(variable) #variable

#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

template <typename T>

void testVector(T& v) {
  REP(i, SZ(v)) {
    cout << i << ":" << v << endl;
  }
}


/* ^^^^^^^^^^^^^^^ Settting Part ^^^^^^^^^^^^^^^ */

/* ---------- Variances ---------- */

ll N, C;
VL x, v;
ll cal = 0;
ll max_c = 0;

VVL part_cal(2, VL(100010, 0));

/* ---------- Functions ---------- */


/* ---------- Main Function ---------- */

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> C;
  x.resize(N + 2);
  v.resize(N + 2);
  NREP(i, N) {
    cin >> x[i] >> v[i];
  }

  x[0] = 0;
  x[N + 1] = C;

  cal = 0;
  NREP(i, N) {
    cal -= x[i] - x[i - 1];
    cal += v[i];
    part_cal[0][i] = max(part_cal[0][i - 1], cal);
  }

  cal = 0;
  RNREP(i, N) {
    cal -= x[i + 1] - x[i];
    cal += v[i];
    part_cal[1][i] = max(part_cal[1][i + 1], cal);
  }

  REP(i, N + 1) {
    max_c = max(max_c, part_cal[0][i]);
    max_c = max(max_c, part_cal[1][i]);
    cal = part_cal[0][i] + part_cal[1][i + 1] - x[i];
    max_c = max(max_c, cal);
    cal = part_cal[0][i] + part_cal[1][i + 1] - C + x[i + 1];
    max_c = max(max_c, cal);
  }

  cout << max_c << endl;

  return 0;
}

Submission Info

Submission Time
Task D - Static Sushi
User Misteer
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3346 Byte
Status
Exec Time 25 ms
Memory 3440 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03, a04
Subtask1 300 / 300 a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29
Subtask2 200 / 200 a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, c30, c31, c32, c33, c34, c35, c36, c37, c38, c39, c40, c41, c42, c43, c44, c45, c46, c47, c48, c49, c50
Case Name Status Exec Time Memory
a01 2 ms 2560 KB
a02 2 ms 2560 KB
a03 2 ms 2560 KB
a04 2 ms 2560 KB
b05 2 ms 2560 KB
b06 2 ms 2560 KB
b07 2 ms 2560 KB
b08 2 ms 2560 KB
b09 2 ms 2560 KB
b10 2 ms 2560 KB
b11 2 ms 2560 KB
b12 2 ms 2560 KB
b13 2 ms 2560 KB
b14 2 ms 2560 KB
b15 2 ms 2560 KB
b16 2 ms 2560 KB
b17 2 ms 2560 KB
b18 2 ms 2560 KB
b19 2 ms 2560 KB
b20 2 ms 2560 KB
b21 2 ms 2560 KB
b22 2 ms 2560 KB
b23 2 ms 2560 KB
b24 2 ms 2560 KB
b25 2 ms 2560 KB
b26 2 ms 2560 KB
b27 2 ms 2560 KB
b28 2 ms 2560 KB
b29 2 ms 2560 KB
c30 16 ms 3440 KB
c31 21 ms 3440 KB
c32 25 ms 3440 KB
c33 25 ms 3440 KB
c34 25 ms 3440 KB
c35 16 ms 3440 KB
c36 25 ms 3440 KB
c37 25 ms 3440 KB
c38 24 ms 3440 KB
c39 24 ms 3440 KB
c40 24 ms 3440 KB
c41 24 ms 3440 KB
c42 25 ms 3440 KB
c43 4 ms 2560 KB
c44 25 ms 3440 KB
c45 2 ms 2560 KB
c46 24 ms 3440 KB
c47 2 ms 2560 KB
c48 24 ms 3440 KB
c49 24 ms 3440 KB
c50 24 ms 3440 KB