Submission #1028235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028235		andrewp	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1060 ms	5464 KiB

divide

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

#define ll int64_t
#define ar array

const int mxN=1e5;
ll n, x[mxN], g[mxN], e[mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> n;
    for(int i=0; i<n; ++i) {
        cin >> x[i] >> g[i] >> e[i];
    }
    ll ans=0;
    for(int i=0; i<n; ++i) {
        ll en=e[i], cur=g[i];
        ans=max(ans, g[i]);
        for(int j=i-1; j>=0; --j) {
            en+=e[j], cur+=g[j];
            if(en>=(x[i]-x[j])) ans=max(ans, cur);
        }
    }
    cout << ans << "\n";
	return 0;
}

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