Submission #1334399

#TimeUsernameProblemLanguageResultExecution timeMemory
1334399sporknivesArt Exhibition (JOI18_art)C++20
100 / 100
518 ms15980 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;

signed main() {
	int n; cin>>n;
	vector<pii> a(n);
	for(int i=0;i<n;i++) {
		int s,v; cin>>s>>v;
		a[i] = {s,v};
	} 
	sort(a.begin(),a.end());
	vector<int> p(n+1);
	p[0]=0;
	for(int i=1;i<=n;i++) {
		p[i] = p[i-1] + a[i-1].second;
	}
	
	//for(int i=0;i<=n;i++) cout<<p[i]<<" ";
	//cout<<"\n";
	
	vector<int> mx(n);
	int cur=LLONG_MIN;
	for(int i=n-1;i>=0;i--) {
		cur = max(cur, p[i+1]-a[i].first);
		mx[i] = cur;
	}
	
	//for(int i=0;i<n;i++) cout<<mx[i]<<" ";
	//cout<<"\n";
	
	int ans=LLONG_MIN;
	for(int i=0;i<n;i++) {
		ans = max(ans, a[i].first-p[i]+mx[i]);
	}
	
	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...