Submission #2392236
Source Code Expand
/** * File : D.cpp * Author : Kazune Takahashi * Created : 2018-4-21 21:12:38 * Powered by Visual Studio Code */ #include <iostream> #include <iomanip> // << fixed << setprecision(xxx) #include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ; #include <vector> #include <string> // to_string(nnn) // substr(m, n) // stoi(nnn) #include <complex> #include <tuple> #include <queue> #include <stack> #include <map> // if (M.find(key) != M.end()) { } #include <set> #include <random> // random_device rd; mt19937 mt(rd()); #include <cctype> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; #define DEBUG 0 // change 0 -> 1 if we need debug. typedef long long ll; // const int dx[4] = {1, 0, -1, 0}; // const int dy[4] = {0, 1, 0, -1}; // const int C = 1e6+10; // const ll M = 1000000007; int N; ll C; ll x[100010]; ll v[100010]; ll w[100010]; ll w_rev[100010]; ll solve() { ll ans = 0; fill(w, w + N, 0); w[0] = v[0]; for (auto i = 1; i < N; i++) { w[i] = w[i - 1] + v[i]; } for (auto i = 0; i < N; i++) { ans = max(ans, w[i] - x[i]); } w_rev[N - 1] = v[N - 1]; for (auto i = N - 2; i >= 0; i--) { w_rev[i] = w_rev[i + 1] + v[i]; } ll maxi = 0; for (auto i = N - 1; i >= 1; i--) { maxi = max(maxi, w_rev[i] - (C - x[i])); ans = max(ans, w[i - 1] - 2 * x[i - 1] + maxi); } maxi = max(maxi, w_rev[0] - (C - x[0])); ans = max(ans, maxi); return ans; } int main() { cin >> N >> C; for (auto i = 0; i < N; i++) { cin >> x[i] >> v[i]; } ll ans = solve(); for (auto i = 0; i < N; i++) { x[i] = C - x[i]; } reverse(v, v + N); reverse(x, x + N); ans = max(ans, solve()); cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - Static Sushi |
User | kazunetakahashi |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 1835 Byte |
Status | AC |
Exec Time | 99 ms |
Memory | 3328 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | 200 / 200 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03, a04 |
Subtask1 | 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 | 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 | AC | 1 ms | 256 KB |
a02 | AC | 1 ms | 256 KB |
a03 | AC | 1 ms | 256 KB |
a04 | AC | 1 ms | 256 KB |
b05 | AC | 1 ms | 256 KB |
b06 | AC | 1 ms | 256 KB |
b07 | AC | 1 ms | 256 KB |
b08 | AC | 1 ms | 256 KB |
b09 | AC | 1 ms | 256 KB |
b10 | AC | 1 ms | 256 KB |
b11 | AC | 1 ms | 256 KB |
b12 | AC | 1 ms | 256 KB |
b13 | AC | 1 ms | 256 KB |
b14 | AC | 1 ms | 256 KB |
b15 | AC | 1 ms | 256 KB |
b16 | AC | 1 ms | 256 KB |
b17 | AC | 1 ms | 256 KB |
b18 | AC | 1 ms | 256 KB |
b19 | AC | 1 ms | 256 KB |
b20 | AC | 1 ms | 256 KB |
b21 | AC | 1 ms | 256 KB |
b22 | AC | 1 ms | 256 KB |
b23 | AC | 1 ms | 256 KB |
b24 | AC | 1 ms | 256 KB |
b25 | AC | 1 ms | 256 KB |
b26 | AC | 1 ms | 256 KB |
b27 | AC | 1 ms | 256 KB |
b28 | AC | 1 ms | 256 KB |
b29 | AC | 1 ms | 256 KB |
c30 | AC | 46 ms | 3328 KB |
c31 | AC | 72 ms | 3328 KB |
c32 | AC | 99 ms | 3328 KB |
c33 | AC | 98 ms | 3328 KB |
c34 | AC | 98 ms | 3328 KB |
c35 | AC | 46 ms | 3328 KB |
c36 | AC | 95 ms | 3328 KB |
c37 | AC | 90 ms | 3328 KB |
c38 | AC | 91 ms | 3328 KB |
c39 | AC | 92 ms | 3328 KB |
c40 | AC | 92 ms | 3328 KB |
c41 | AC | 90 ms | 3328 KB |
c42 | AC | 91 ms | 3328 KB |
c43 | AC | 10 ms | 512 KB |
c44 | AC | 91 ms | 3328 KB |
c45 | AC | 2 ms | 256 KB |
c46 | AC | 89 ms | 3328 KB |
c47 | AC | 1 ms | 256 KB |
c48 | AC | 93 ms | 3328 KB |
c49 | AC | 90 ms | 3328 KB |
c50 | AC | 92 ms | 3328 KB |