Submission #1091816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091816		alex2407	Divide and conquer (IZhO14_divide)	C++17	48 / 100	1060 ms	3416 KiB

divide

#include <iostream>

using namespace std;

long long a[3][110000], g[110000], en[110000];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, ans = 0;
    cin >> n;
    g[0] = 0;
    en[0] = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[0][i] >> a[1][i] >> a[2][i];
        g[i + 1] = g[i] + a[1][i];
        en[i + 1] = en[i] + a[2][i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (a[0][j] - a[0][i] <= en[j + 1] - en[i + 1] + a[2][i]) {
                ans = max(ans, g[j + 1] - g[i + 1] + a[1][i]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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