Submission #1106295

#TimeUsernameProblemLanguageResultExecution timeMemory
1106295akzytrArt Exhibition (JOI18_art)C++17
100 / 100
357 ms28744 KiB
#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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...