Submission #685888

#	Time	Username	Problem	Language	Result	Execution time	Memory
685888		GudStonks	Divide and conquer (IZhO14_divide)	C++17	100 / 100	32 ms	6232 KiB

divide

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ft first
#define sd second
const ll MOD = 1e9+7;
ll n, ans, pr[200005], p[200005], d[200005], g[200005];

void fun(){
	cin>>n;
	for(ll i = 1, a, b, c, l = 0; i <= n; i++){
		cin>>a>>b>>c;
		if(i == 1)l = a;
		pr[i] = pr[i - 1] + c - (a - l);
		p[i] = c;
		d[i] = (a - l);
		g[i] = b + g[i - 1];
		l = a;
	}
	for(ll i = n - 1; i; i--)pr[i] = max(pr[i], pr[i + 1]);
	for(ll i = 1, sum = 0; i <= n; i++){
		ll l = i, r = n, res = 0;
		while(r >= l){
			ll m = (l + r) / 2;
			if(pr[m] - sum >= 0)
				l = m + 1, res = m;
			else
				r = m - 1;
		}
		ans = max(ans, g[res] - g[i - 1]);
		sum += p[i] - d[i + 1];
	}
	cout<<ans<<endl;
}

int  main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int ttt = 1;
	//cin>>ttt;
	while(ttt--)fun();
}

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