제출 #1344969

#제출 시각아이디문제언어결과실행 시간메모리
1344969jumpArt Exhibition (JOI18_art)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define int long long
std::vector<std::pair<int,int>> v;
int sizeA[500500];
int costA[500500];
int prefC[500500];
signed main(){
	int ans=0;
	int n;
	std::cin >> n;
	for(int i=0;i<n;i++){
		int size,cost;
		std::cin >> size >> cost;
		ans=std::max(ans,cost);
		v.push_back({size,cost});
	}
	std::sort(v.begin(),v.end());
	for(int i=1;i<=n;i++){
		sizeA[i]=v[i-1].first;
		costA[i]=v[i-1].second;
		prefC[i]=costA[i]+prefC[i-1];
	}
	int l=1,c=1;
	for(int r=1;r<=n;r++){
		ans=std::max(ans,(prefC[r]-prefC[l-1])-(sizeA[r]-sizeA[l]));
		//std::cout << (prefC[r]-prefC[l-1])-(sizeA[r]-sizeA[l]) <<'|' << (prefC[r]-prefC[l-1]) << '|' << (sizeA[r]-sizeA[l]) <<'\n';
		while(l+c<r){
			if(sizeA[l+c]-sizeA[l]>=prefC[l+c]-prefC[l-1]){
				l=l+c;
				c=1;
			}
			else c++;
			//std::cout << (prefC[r]-prefC[l-1])-(sizeA[r]-sizeA[l]) <<'|' << (prefC[r]-prefC[l-1]) << '|' << (sizeA[r]-sizeA[l]) <<' ';
			//std::cout << r << ' ' << l << ' ' << c << '\n';
		}
		ans=std::max(ans,(prefC[r]-prefC[l-1])-(sizeA[r]-sizeA[l]));
	}
	std::cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...