Submission #136596

#TimeUsernameProblemLanguageResultExecution timeMemory
136596FedericoSDivide and conquer (IZhO14_divide)C++14
48 / 100
1080 ms4188 KiB
#include <iostream>
#include <set>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;

ll N;
ll X[1000006],G[1000006],D[1000006];
ll A[1000006];
ll Gsum[1000006],Dsum[1000006];
ll ans,best;
set<pii> S;

ll query(ll x){
	ll res=0;
	for(pii p:S)
		if(p.second>=x)
			res=max(res,p.first);
	return res;
}

int main(){
	cin>>N;
	for(ll i=1;i<N+1;i++){
		cin>>X[i]>>G[i]>>D[i];
		Gsum[i]=Gsum[i-1]+G[i];
		Dsum[i]=Dsum[i-1]+D[i];
	}

	for(ll i=N;i>0;i--){
		S.insert({Gsum[i],Dsum[i]-X[i]});
		ans=max(ans,query(Dsum[i-1]-X[i])-Gsum[i-1]);
	}

	cout<<ans;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...