oj.uz

Submission #37401

# Submission time Handle Problem Language Result Execution time Memory
37401 2017-12-25T05:00:36 Z HardNut Divide and conquer (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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