oj.uz

답안 #13127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13127 2015-01-31T12:54:43 Z gs14004 금 캐기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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