# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
763413 | 2023-06-22T09:36:12 Z | KN200711 | Divide and conquer (IZhO14_divide) | C++14 | 27 ms | 5952 KB |
# include <bits/stdc++.h> # define ll long long # define fi first # define se second using namespace std; int main() { int N; scanf("%d", &N); vector<int> x(N), y(N), z(N); for(int i=0;i<N;i++) scanf("%d %d %d", &x[i], &y[i], &z[i]); ll pref = 0ll; vector< pair<ll, ll> > as; as.clear(); ll ans = 0ll, nw = 0ll; for(int i=0;i<N;i++) { if(as.size() == 0 || -as.back().fi > pref - 1ll * x[i]) as.push_back(make_pair(-pref + 1ll * x[i], nw)); nw += y[i]; pref += z[i]; ll ck = pref - x[i]; // cout<<ck<<endl; int P = lower_bound(as.begin(), as.end(), make_pair(-ck, 0ll)) - as.begin(); if(P == as.size()) continue; ans = max(ans, nw - as[P].se); } printf("%lld\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 304 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 304 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 304 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 312 KB | Output is correct |
21 | Correct | 1 ms | 340 KB | Output is correct |
22 | Correct | 1 ms | 340 KB | Output is correct |
23 | Correct | 2 ms | 568 KB | Output is correct |
24 | Correct | 2 ms | 596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 304 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 304 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 312 KB | Output is correct |
21 | Correct | 1 ms | 340 KB | Output is correct |
22 | Correct | 1 ms | 340 KB | Output is correct |
23 | Correct | 2 ms | 568 KB | Output is correct |
24 | Correct | 2 ms | 596 KB | Output is correct |
25 | Correct | 1 ms | 312 KB | Output is correct |
26 | Correct | 3 ms | 468 KB | Output is correct |
27 | Correct | 3 ms | 596 KB | Output is correct |
28 | Correct | 12 ms | 1908 KB | Output is correct |
29 | Correct | 14 ms | 2160 KB | Output is correct |
30 | Correct | 27 ms | 4272 KB | Output is correct |
31 | Correct | 21 ms | 3156 KB | Output is correct |
32 | Correct | 25 ms | 3380 KB | Output is correct |
33 | Correct | 21 ms | 3000 KB | Output is correct |
34 | Correct | 25 ms | 4292 KB | Output is correct |
35 | Correct | 27 ms | 5800 KB | Output is correct |
36 | Correct | 27 ms | 5952 KB | Output is correct |