Submission #1347616

#TimeUsernameProblemLanguageResultExecution timeMemory
1347616jumpDivide and conquer (IZhO14_divide)C++20
100 / 100
18 ms5104 KiB
#include <bits/stdc++.h>
#define int long long

int n;
int cord[100010];
int gold[100010];
int energy[100010];

int prefGold[100010];
int prefEnergy[100010];
int best[100010];

signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	std::cin >> n;
	for(int i=1;i<=n;i++){
		std::cin >> cord[i] >> gold[i] >> energy[i];
		prefGold[i]=prefGold[i-1]+gold[i];
		prefEnergy[i]=prefEnergy[i-1]+energy[i];
	}

	for(int i=1;i<=n;i++){
		best[i]=prefEnergy[i]-cord[i];
	}

	for(int i=n-1;i>=1;i--){
		best[i]=std::max(best[i],best[i+1]);
	}

	int ans=0;

	for(int i=1;i<=n;i++){
		int need=prefEnergy[i-1]-cord[i];

		int l=i,r=n;
		while(l<r){
			int m=(l+r+1)/2;
			if(best[m]>=need)l=m;
			else r=m-1;
		}

		if(best[l]>=need){
			ans=std::max(ans,prefGold[l]-prefGold[i-1]);
		}
	}

	std::cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...