Submission #1255101

#TimeUsernameProblemLanguageResultExecution timeMemory
1255101ciao_gioArt Exhibition (JOI18_art)C++20
100 / 100
384 ms18036 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
	int N;
	cin >> N;

	vector<ll> A(N), B(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
	}

	vector<int> idx(N);
	iota(begin(idx), end(idx), 0);
	sort(begin(idx), end(idx), [&](int i, int j) { return A[i] < A[j]; });

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

	vector<ll> sf(N); sf[N - 1] = pf[N - 1];
	for (int i = N - 1; i > 0; i--) {
		sf[i - 1] = max(pf[i - 1], sf[i]);
	}

	ll ans = 0;
	for (int i = 0; i < N; i++) {
		ans = max(ans, sf[i] - pf[i] + B[idx[i]]);
	}

	cout << ans << '\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...