oj.uz

Submission #13127

# Submission time Handle Problem Language Result Execution time Memory
13127 2015-01-31T12:54:43 Z gs14004 Divide and conquer (IZhO14_divide) C++14
100 / 100
 63 ms 4208 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

int n;
long long x[100005], g[100005], d[100005], p[100005];

int main(){
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%lld %lld %lld",&x[i],&g[i],&d[i]);
        d[i] += d[i-1];
        g[i] += g[i-1];
        p[i] = d[i] - x[i];
    }
    for (int i=n-1; i; i--) {
        p[i] = max(p[i],p[i+1]);
    }
    long long r = 0;
    for (int i=1; i<=n; i++) {
        int s = i, e = n;
        while (s != e) {
            int m = (s+e+1)/2;
            if(d[i-1] - x[i] <= p[m]) s = m;
            else e = m-1;
        }
        if(d[i-1] - x[i] <= p[s]){
            r = max(r,g[s] - g[i-1]);
        }
    }
    printf("%lld",r);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4208 KB Output is correct
2 Correct 0 ms 4208 KB Output is correct
3 Correct 0 ms 4208 KB Output is correct
4 Correct 0 ms 4208 KB Output is correct
5 Correct 0 ms 4208 KB Output is correct
6 Correct 0 ms 4208 KB Output is correct
7 Correct 0 ms 4208 KB Output is correct
8 Correct 0 ms 4208 KB Output is correct
9 Correct 0 ms 4208 KB Output is correct
10 Correct 0 ms 4208 KB Output is correct
11 Correct 0 ms 4208 KB Output is correct
12 Correct 0 ms 4208 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4208 KB Output is correct
2 Correct 0 ms 4208 KB Output is correct
3 Correct 0 ms 4208 KB Output is correct
4 Correct 0 ms 4208 KB Output is correct
5 Correct 0 ms 4208 KB Output is correct
6 Correct 0 ms 4208 KB Output is correct
7 Correct 0 ms 4208 KB Output is correct
8 Correct 0 ms 4208 KB Output is correct
9 Correct 0 ms 4208 KB Output is correct
10 Correct 0 ms 4208 KB Output is correct
11 Correct 3 ms 4208 KB Output is correct
12 Correct 3 ms 4208 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4208 KB Output is correct
2 Correct 3 ms 4208 KB Output is correct
3 Correct 5 ms 4208 KB Output is correct
4 Correct 23 ms 4208 KB Output is correct
5 Correct 23 ms 4208 KB Output is correct
6 Correct 37 ms 4208 KB Output is correct
7 Correct 57 ms 4208 KB Output is correct
8 Correct 59 ms 4208 KB Output is correct
9 Correct 47 ms 4208 KB Output is correct
10 Correct 33 ms 4208 KB Output is correct
11 Correct 63 ms 4208 KB Output is correct
12 Correct 44 ms 4208 KB Output is correct