Submission #765032

#	Time	Username	Problem	Language	Result	Execution time	Memory
765032		yusuf12360	Art Exhibition (JOI18_art)	C++14	100 / 100	176 ms	28620 KiB

art

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50