Submission #687682

#TimeUsernameProblemLanguageResultExecution timeMemory
687682NK_Art Exhibition (JOI18_art)C++17
100 / 100
242 ms28648 KiB
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	vector<ll> A(N); vector<int> B(N);
	for(int i = 0; i < N; i++) cin >> A[i] >> B[i];

	vector<int> I(N); iota(begin(I), end(I), 0);
	sort(begin(I), end(I), [&](int x, int y) {
		return A[x] < A[y];
	});

	vector<ll> P(N);
	for(int i = 0; i < N; i++) {
		P[i] += -A[I[i]] + B[I[i]];
		if (i+1 < N) P[i+1] += A[I[i]];
	}

	for(int i = 1; i < N; i++) P[i] += P[i-1];

	ll ans = 0, S = 0;
	

	vector<ll> mx = P; for(int i = N-2; i >= 0; i--) mx[i] = max(mx[i], mx[i+1]);

	for(int i = 0; i < N; i++) {
		ll res = mx[i] - S + A[I[i]]; S += B[I[i]];
		ans = max(ans, res);
	}

	cout << ans << nl;


    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...