# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
37796 | 2017-12-28T06:34:48 Z | Just_Solve_The_Problem | Divide and conquer (IZhO14_divide) | C++11 | 1000 ms | 5920 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = (int)1e5 + 7; ll x[N], g[N], d[N]; ll pg[N], pd[N]; bool check (int l, int r) { return x[r] - x[l] <= pd[r] - pd[l - 1]; } main () { int n; scanf ("%d", &n); for (int i = 1; i <= n; i++) { scanf ("%lld %lld %lld", x + i, g + i, d + i); } for (int i = 1; i <= n; i++) { pg[i] = pg[i - 1] + g[i]; pd[i] = pd[i - 1] + d[i]; } ll ans = 0; for (int i = n; i >= 1; i--) { if (pg[n] - pg[i - 1] <= ans) continue; for (int j = i; j <= n; j++) { if (check(i, j)) { ans = max(ans, pg[j] - pg[i - 1]); } } } cout << ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5920 KB | Output is correct |
2 | Correct | 0 ms | 5920 KB | Output is correct |
3 | Correct | 0 ms | 5920 KB | Output is correct |
4 | Correct | 0 ms | 5920 KB | Output is correct |
5 | Correct | 0 ms | 5920 KB | Output is correct |
6 | Correct | 0 ms | 5920 KB | Output is correct |
7 | Correct | 0 ms | 5920 KB | Output is correct |
8 | Correct | 0 ms | 5920 KB | Output is correct |
9 | Correct | 0 ms | 5920 KB | Output is correct |
10 | Correct | 0 ms | 5920 KB | Output is correct |
11 | Correct | 0 ms | 5920 KB | Output is correct |
12 | Correct | 0 ms | 5920 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5920 KB | Output is correct |
2 | Correct | 0 ms | 5920 KB | Output is correct |
3 | Correct | 0 ms | 5920 KB | Output is correct |
4 | Correct | 0 ms | 5920 KB | Output is correct |
5 | Correct | 0 ms | 5920 KB | Output is correct |
6 | Correct | 0 ms | 5920 KB | Output is correct |
7 | Correct | 0 ms | 5920 KB | Output is correct |
8 | Correct | 0 ms | 5920 KB | Output is correct |
9 | Correct | 0 ms | 5920 KB | Output is correct |
10 | Correct | 3 ms | 5920 KB | Output is correct |
11 | Correct | 13 ms | 5920 KB | Output is correct |
12 | Correct | 13 ms | 5920 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 5920 KB | Output is correct |
2 | Correct | 79 ms | 5920 KB | Output is correct |
3 | Correct | 79 ms | 5920 KB | Output is correct |
4 | Execution timed out | 1000 ms | 5920 KB | Execution timed out |
5 | Halted | 0 ms | 0 KB | - |