Submission #134717

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

divide

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
ll gold[maxn], energy[maxn], x[maxn], n;
ll prefix_g[maxn], prefix_e[maxn];

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>x[i]>>gold[i]>>energy[i];

		prefix_g[i] = prefix_g[i-1] + gold[i];
		prefix_e[i] = prefix_e[i-1] + energy[i];
	}

	ll result = 0LL;
	for(int i=1;i<=n;i++) {
		for(int j=i;j>=1;j--) {
			if(x[i] - x[j] <= prefix_e[i] - prefix_e[j-1]) {
				result = max(result, prefix_g[i] - prefix_g[j-1]);
			}
		}
	}
	cout<<result<<"\n";
}

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