제출 #765032

#제출 시각아이디문제언어결과실행 시간메모리
765032yusuf12360Art Exhibition (JOI18_art)C++14
100 / 100
176 ms28620 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector<pair<int, int>> a(n);
	for(auto &p : a) cin >> p.first >> p.second;
	sort(a.begin(), a.end());
	vector<int> suf(n);
	suf[n-1]=a[n-1].first+a[n-1].second;
	for(int i=n-2; i>=0; i--)
		suf[i]=suf[i+1]+a[i].second-a[i+1].first+a[i].first;
	vector<int> pre_max(n);
	pre_max[0]=suf[0];
	for(int i=1; i<n; i++) pre_max[i]=max(suf[i], pre_max[i-1]);
	int sum=0, cost=-1e17;
	for(int i=n-1; i>=0; i--)
		cost=max(cost, pre_max[i]-sum-a[i].first),
		sum+=a[i].second;
	cout << cost << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...