Submission #372489

#TimeUsernameProblemLanguageResultExecution timeMemory
372489mariowongDivide and conquer (IZhO14_divide)C++14
100 / 100
43 ms8172 KiB
#include <bits/stdc++.h>
using namespace std;

long long mn,n,m,pt,ans;
pair<long long,long long> f[100005];
long long d[100005],a[100005],e[100005],ps[100005],ttl[100005];
long long l,r,mid;
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> d[i] >> a[i] >> e[i];
		ps[i]=ps[i-1]+e[i];
		ttl[i]=ttl[i-1]+a[i];
	}
	mn=1e18;
	for (int i=n;i>=1;i--){
		if (d[i]-ps[i] < mn){
			mn=d[i]-ps[i];
			pt++; f[pt]=make_pair(d[i]-ps[i],i);
		}
		l=1; r=pt;
		while (l < r){
			mid=(l+r)/2;
			if (f[mid].first <= d[i]-ps[i-1])
			r=mid;
			else
			l=mid+1;
		} 
		ans=max(ans,ttl[f[l].second]-ttl[i-1]);
	} 
	cout << ans << "\n";
	return 0;
}	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...