# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
80979 | 2018-10-23T10:31:17 Z | farukkastamonuda | Divide and conquer (IZhO14_divide) | C++14 | 68 ms | 4464 KB |
#include <bits/stdc++.h> #define fi first #define se second #define lo long long #define inf 1000000000 #define md 1000000007 #define li 100005 #define mp make_pair #define pb push_back using namespace std; int n; lo int x[li], g[li], d[li], sume[li], sumg[li], cev; bool check(int val, int beg){ if(x[val] - x[beg] <= sume[val] - sume[beg - 1]) return true; return false; } int main(){ scanf("%d", &n); for(int i = 1; i <= n; i ++){ scanf("%lld %lld %lld", &x[i], &g[i], &d[i]); sume[i] = sume[i - 1] + d[i]; sumg[i] = sumg[i - 1] + g[i]; } for(int i = 1; i <= n; i ++){ int bas = i, son = n; while(bas <= son){ int mid = (bas + son) / 2; if(check(mid, i)) bas = mid + 1; else son = mid - 1; } cev = max(cev, sumg[son] - sumg[i - 1]); } printf("%lld\n", cev); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 456 KB | Output is correct |
3 | Correct | 2 ms | 644 KB | Output is correct |
4 | Correct | 2 ms | 644 KB | Output is correct |
5 | Correct | 2 ms | 644 KB | Output is correct |
6 | Correct | 2 ms | 644 KB | Output is correct |
7 | Correct | 2 ms | 644 KB | Output is correct |
8 | Correct | 2 ms | 644 KB | Output is correct |
9 | Correct | 2 ms | 644 KB | Output is correct |
10 | Correct | 3 ms | 644 KB | Output is correct |
11 | Correct | 2 ms | 644 KB | Output is correct |
12 | Correct | 2 ms | 644 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 644 KB | Output is correct |
2 | Correct | 2 ms | 644 KB | Output is correct |
3 | Incorrect | 2 ms | 644 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 696 KB | Output is correct |
2 | Correct | 6 ms | 952 KB | Output is correct |
3 | Correct | 7 ms | 952 KB | Output is correct |
4 | Correct | 26 ms | 2468 KB | Output is correct |
5 | Correct | 31 ms | 2488 KB | Output is correct |
6 | Correct | 68 ms | 4432 KB | Output is correct |
7 | Correct | 48 ms | 4448 KB | Output is correct |
8 | Correct | 52 ms | 4464 KB | Output is correct |
9 | Correct | 44 ms | 4464 KB | Output is correct |
10 | Incorrect | 45 ms | 4464 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |