Submission #17448

#	Time	Username	Problem	Language	Result	Execution time	Memory
17448		elgun1999	Divide and conquer (IZhO14_divide)	C++98	100 / 100	68 ms	6408 KiB

divide

#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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52