oj.uz

답안 #37401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37401 2017-12-25T05:00:36 Z HardNut 금 캐기 (IZhO14_divide) C++14
100 / 100
 386 ms 6864 KB 
#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e5 + 5;

typedef long long ll;

ll ans, n, x[N], g[N], e[N];
ll t[N];
ll dpp[N], dp[N];

void build(int v, int L, int R) {
    if (L == R) {
        t[v] =  dpp[L - 1] - x[L];
        return;
    }
    int md = (L + R) >> 1;
    build(v * 2, L, md);
    build(v * 2 + 1, md + 1, R);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

ll get(int v, int L, int R, int l, int r) {
    if (L > r || l > R)
        return 1e9 + 5;
    if (l <= L && R <= r)
        return t[v];
    int md = (L + R) >> 1;
    return min(get(v * 2, L, md, l, r), get(v * 2 + 1, md + 1, R, l, r));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> g[i] >> e[i];
        dp[i] = dp[i - 1] + g[i];
        dpp[i] = dpp[i - 1] + e[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        int l = 0, r = i;
        while (r - l > 1) {
            int md = (l + r) >> 1;
            if (get(1, 1, n, 1, md) <= dpp[i] - x[i]) {
                r = md;
            } else {
                l = md;
            }
        }
        ans = max(ans, dp[i] - dp[r - 1]);
    }
    cout << ans;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6864 KB Output is correct
2 Correct 0 ms 6864 KB Output is correct
3 Correct 0 ms 6864 KB Output is correct
4 Correct 0 ms 6864 KB Output is correct
5 Correct 0 ms 6864 KB Output is correct
6 Correct 0 ms 6864 KB Output is correct
7 Correct 0 ms 6864 KB Output is correct
8 Correct 0 ms 6864 KB Output is correct
9 Correct 0 ms 6864 KB Output is correct
10 Correct 0 ms 6864 KB Output is correct
11 Correct 0 ms 6864 KB Output is correct
12 Correct 0 ms 6864 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6864 KB Output is correct
2 Correct 0 ms 6864 KB Output is correct
3 Correct 0 ms 6864 KB Output is correct
4 Correct 0 ms 6864 KB Output is correct
5 Correct 0 ms 6864 KB Output is correct
6 Correct 3 ms 6864 KB Output is correct
7 Correct 0 ms 6864 KB Output is correct
8 Correct 0 ms 6864 KB Output is correct
9 Correct 0 ms 6864 KB Output is correct
10 Correct 3 ms 6864 KB Output is correct
11 Correct 6 ms 6864 KB Output is correct
12 Correct 13 ms 6864 KB Output is correct

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6864 KB Output is correct
2 Correct 16 ms 6864 KB Output is correct
3 Correct 16 ms 6864 KB Output is correct
4 Correct 123 ms 6864 KB Output is correct
5 Correct 123 ms 6864 KB Output is correct
6 Correct 316 ms 6864 KB Output is correct
7 Correct 309 ms 6864 KB Output is correct
8 Correct 276 ms 6864 KB Output is correct
9 Correct 266 ms 6864 KB Output is correct
10 Correct 343 ms 6864 KB Output is correct
11 Correct 373 ms 6864 KB Output is correct
12 Correct 386 ms 6864 KB Output is correct