Submission #247411

#	Time	Username	Problem	Language	Result	Execution time	Memory
247411		Berted	Art Exhibition (JOI18_art)	C++14	100 / 100	321 ms	28884 KiB

art

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

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