Submission #136598

#	Time	Username	Problem	Language	Result	Execution time	Memory
136598		FedericoS	Divide and conquer (IZhO14_divide)	C++14	100 / 100	279 ms	12664 KiB

divide

#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;
multiset<pii> S;

ll query(ll x){
	return S.lower_bound({x,-1})->second;
}

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({Dsum[i]-X[i],Gsum[i]});

		bool flag=true;
		auto p=S.find({Dsum[i]-X[i],Gsum[i]});

		p++;
		if(p!=S.end()){
			if(p->second>=Gsum[i]){
				p--;
				S.erase(p);
				flag=false;
			}
		}

		p=S.find({Dsum[i]-X[i],Gsum[i]});
		p--;

		if(flag)
			for(;p!=S.begin();p--){
				auto q=p;
				q--;
				if(q->second>Gsum[i])
					break;
				S.erase(q);
			}

		ans=max(ans,query(Dsum[i-1]-X[i])-Gsum[i-1]);
	}

	cout<<ans;

}

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