oj.uz

Submission #17448

# Submission time Handle Problem Language Result Execution time Memory
17448 2015-12-13T12:13:10 Z elgun1999 Divide and conquer (IZhO14_divide) C++
100 / 100
 68 ms 6408 KB 
#include <iostream>
#include <algorithm>
#include <cstdio>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ll long long

using namespace std;

ll n, x[100005], g[100005], e[100005], p[100005], ans;
pair<ll, ll> d[100005];

int main()
{
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &x[i], &g[i], &e[i]);
        g[i] += g[i - 1], e[i] += e[i - 1];
        d[i] = {e[i] - x[i], i};
    }
    sort(d + 1, d + n + 1);
    for (int i = n; i >= 1; i--)
        p[i] = max(p[i + 1], d[i].s);

    for (int i = 1; i <= n; i++) {
        int a = e[i - 1] - x[i];
        int l = 0, r = n + 1;
        while(r - l > 1) {
            int mid = (l + r) / 2;
            if (d[mid].f >= a) r = mid;
            else l = mid;
        }
        a = p[r];
        ans = max(ans, g[a] - g[i - 1]);
    }
    cout << ans;

    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6408 KB Output is correct
2 Correct 6 ms 6408 KB Output is correct
3 Correct 0 ms 6408 KB Output is correct
4 Correct 21 ms 6408 KB Output is correct
5 Correct 32 ms 6408 KB Output is correct
6 Correct 68 ms 6408 KB Output is correct
7 Correct 46 ms 6408 KB Output is correct
8 Correct 46 ms 6408 KB Output is correct
9 Correct 53 ms 6408 KB Output is correct
10 Correct 55 ms 6408 KB Output is correct
11 Correct 50 ms 6408 KB Output is correct
12 Correct 56 ms 6408 KB Output is correct