oj.uz

Submission #13126

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

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

struct cmp{
    bool operator()(int a, int b){
        return a > b;
    }
};

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];
        piv[i] = d[i] - x[i];
    }
    for (int i=n-1; i; i--) {
        piv[i] = max(piv[i],piv[i+1]);
    }
    long long r = 0;
    for (int i=1; i<=n; i++) {
        auto pt = upper_bound(piv+1,piv+n+1,x[i] - d[i-1],cmp());
        pt--;
        r = max(r,g[(pt - piv)] - g[i-1]);
    }
    printf("%lld",r);
}

Subtask #1
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4208 KB Output is correct
2 Incorrect 0 ms 4208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.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 Incorrect 0 ms 4208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4208 KB Output is correct
2 Correct 2 ms 4208 KB Output is correct
3 Incorrect 2 ms 4208 KB Output isn't correct
4 Halted 0 ms 0 KB -