제출 #136598

#제출 시각아이디문제언어결과실행 시간메모리
136598FedericoS금 캐기 (IZhO14_divide)C++14
100 / 100
279 ms12664 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;
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;

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