Submission #344715

#	Time	Username	Problem	Language	Result	Execution time	Memory
344715		bachaquer	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1092 ms	2540 KiB

divide

#include <bits/stdc++.h>
 
#define ll long long
#define pb push_back
 
using namespace std;
 
ll n, x, g, d;
 
int main() {
    cin >> n;
    ll prefd[n], prefg[n], xx[n];
    for (int i = 0; i < n; i++) {
        cin >> x >> g >> d;
        xx[i] = x;
        if (i == 0) {
            prefg[i] = g;
            prefd[i] = d;
        }
        else {
            prefd[i] = prefd[i - 1] + d;
            prefg[i] = prefg[i - 1] + g;
        }
    }
    ll mx = 0;
    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j >= i; j--) {
            if (i == 0){
                if (xx[j] - xx[i] <= prefd[j]) {
                    mx = max(mx, prefg[j]);
                }
            } else if (xx[j] - xx[i] <= prefd[j] - prefd[i - 1]) {
                mx = max(mx, prefg[j] - prefg[i - 1]);
            }
        }
    }
    cout << mx;
    return 0;
}

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