Submission #1106295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106295		akzytr	Art Exhibition (JOI18_art)	C++17	100 / 100	357 ms	28744 KiB

art

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define arr array
#define vec vector
#define sz(a) ((int)(a).size())

void p2() {
	/*
	2 3  ->
	4 5  -> 4
	11 2 -> 0
	*/
	int N;
	cin >> N;
	vector<arr<ll, 2>> AB(N);
	// arr<int, 2> AB[N];
	for(int i = 0; i < N; i++) {
		cin >> AB[i][0] >> AB[i][1];
	}
	sort(AB.begin(), AB.end());

	ll pref[N + 1];
	pref[0] = 0;
	for(int i = 1; i <= N; i++) {
		pref[i] = pref[i - 1] + AB[i - 1][1];
	}

	ll sufmax[N + 2];
	sufmax[N + 1] = -9e18;
	for(int i = N; i >= 1; i--) {
		sufmax[i] = max(sufmax[i + 1], pref[i] - AB[i - 1][0]);
	}
	ll ans = -9e18;

	for(int i = 1; i <= N; i++) {
		ans = max(ans, sufmax[i] - pref[i - 1] + AB[i - 1][0]);
	}
	cout << ans << endl;
}
int main() {
	p2();
}

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