Submission #344717

#	Time	Username	Problem	Language	Result	Execution time	Memory
344717		bachaquer	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1088 ms	1516 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];
    ll mx = 0;
    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;
        }
        for (int j = 0; j <= i; j++) {
            if (j == 0){
                if (xx[i] - xx[j] <= prefd[i]) {
                    mx = max(mx, prefg[i]);
                }
            } 
            else if (xx[i] - xx[j] <= prefd[i] - prefd[j - 1]) {
                mx = max(mx, prefg[i] - prefg[j - 1]);
            }
        }
    }
    
    cout << mx;
    return 0;
}

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