Submission #247411

#TimeUsernameProblemLanguageResultExecution timeMemory
247411BertedArt Exhibition (JOI18_art)C++14
100 / 100
321 ms28884 KiB
#include <iostream>
#include <algorithm>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second
using namespace std;

int n; 
pii ar[500001];
ll pref[500001], mx[500001] = {}, res = 0;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> ar[i].fst >> ar[i].snd;
	sort(ar, ar + n);
	for (int i = 1; i <= n; i++) 
	{
		pref[i] = pref[i - 1] + ar[i - 1].snd - ar[i - 1].fst + ((i > 1) ? ar[i - 2].fst : 0);
	}
	mx[n] = pref[n];
	for (int i = n - 1; i > 0; i--) {mx[i] = max(mx[i + 1], pref[i]);}
	for (int i = 1; i <= n; i++)
	{
		res = max(res, mx[i] - pref[i] + ar[i - 1].snd);
	}
	cout << res << "\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...