제출 #1347583

#제출 시각아이디문제언어결과실행 시간메모리
1347583jump금 캐기 (IZhO14_divide)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define int long long
int n;
int cord[100010];
int gold[100010];
int pref[100010];
int get(int l,int r){
	if(l==0)return pref[r];
	return pref[r]-pref[l-1];
}
int energy[100010];
int ans = 0;
void process(int l,int r,int mid,std::vector<int>& left,std::vector<int>& right){
	int constant = cord[mid+1]-cord[mid];
	// std::cout << constant << '|';
	// for(auto ln:left)std::cout << ln << ' ';
	// std::cout << '|';
	// for(auto rn:right)std::cout << rn << ' ';
	// std::cout << '\n';
	for(int i=l;i<=mid;i++){
		int lb=mid+1,rb=r;
		int midbs=(lb+rb+1)/2;
		while(lb<rb){
			if(left[i-l]+right[midbs-mid-1]-constant>=0){
				lb=midbs;
			}
			else{
				rb=midbs-1;
			}
		}
		if(left[i-l]+right[lb-mid-1]-constant>=0)
		ans=std::max(ans,get(i,lb));
		//std::cout << left[i-l]+right[lb-mid-1]-constant << '*' << i << ' ' << lb << ' ' << get(i,lb) << '\n';
	}
}
void recurseRight(int l,int r,std::vector<int>& rre);
void recurseLeft(int l,int r,std::vector<int>& lre){
	lre.assign(r-l+1,-1e18);
	for(int i=l;i<=r;i++){
		if(i==l)
		lre[i-l]=energy[i];
		else
		lre[i-l]=(lre[i-l-1]+energy[i]-(cord[i]-cord[i-1]));
	}
	int max=-1e18;
	for(int i=r;i>=l;i--)max=std::max(max,lre[i-l]),lre[i-l]=std::max(max,lre[i-l]);
	if(l==r)return;
	std::vector<int> left;
	std::vector<int> right;
	int mid=(l+r)/2;
	recurseRight(l,mid,left);
	//low to high
	recurseLeft(mid+1,r,right);
	//high to low
	process(l,r,mid,left,right);
}
void recurseRight(int l,int r,std::vector<int>& rre){
	rre.assign(r-l+1,-1e18);
	for(int i=r;i>=l;i--){
		if(i==r)
		rre[i-l]=energy[i];
		else
		rre[i-l]=(rre[i-l+1]+energy[i]-(cord[i+1]-cord[i]));
	}
	int max=-1e18;
	for(int i=l;i<=r;i++)max=std::max(max,rre[i-l]),rre[i-l]=std::max(max,rre[i-l]);
	if(l==r)return;
	std::vector<int> left;
	std::vector<int> right;
	int mid=(l+r)/2;
	recurseRight(l,mid,left);
	//low to high
	recurseLeft(mid+1,r,right);
	//high to low
	process(l,r,mid,left,right);
}
signed main(){
	std::cin >> n;
	for(int i=1;i<=n;i++){
		std::cin >> cord[i] >> gold[i] >> energy[i];
		pref[i]=pref[i-1]+gold[i];
	}
	std::vector<int> e;
	recurseLeft(1,n,e);
	std::cout << ans << '\n';
}
/*
4
0 5 1
1 7 2
4 4 1
7 15 1
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...