Submission #1010886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010886		phoenix	Divide and conquer (IZhO14_divide)	C++17	100 / 100	38 ms	5980 KiB

divide

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n;
int x[N], g[N], d[N];

long long sum[N];
long long val[N];

long long recur(int l, int r) {
    if (l == r) {
        return g[l];
    }
    int mid = (l + r) / 2;
    long long s;
    s = 0; 
    sum[l] = sum[r] = 0;
    for (int i = mid; i >= l; i--) {
        sum[i] = (sum[l] += g[i]);
        s += d[i];
        val[i] = s + x[i];
    }
    s = 0;
    for (int i = mid + 1; i <= r; i++) {
        sum[i] = (sum[r] += g[i]);
        s += d[i];
        val[i] = x[i] - s;
    }
    for (int i = r; i > mid + 1; i--) 
        val[i - 1] = min(val[i - 1], val[i]);
    
    long long res = 0;
    for (int i = mid; i >= l; i--) {
        int lb = mid, rb = r + 1;
        while (rb - lb > 1) {
            int m = (lb + rb) / 2;
            if (val[m] <= val[i]) lb = m;
            else rb = m;
        }
        if (lb > mid) res = max(res, sum[i] + sum[lb]);
    }
    res = max(res, recur(l, mid));
    res = max(res, recur(mid + 1, r));
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> g[i] >> d[i];
    }
    cout << recur(0, n - 1);
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52