Submission #372489

#	Time	Username	Problem	Language	Result	Execution time	Memory
372489		mariowong	Divide and conquer (IZhO14_divide)	C++14	100 / 100	43 ms	8172 KiB

divide

#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;
}	

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