Submission #1273640

#TimeUsernameProblemLanguageResultExecution timeMemory
1273640kaiboyArt Exhibition (JOI18_art)C++20
100 / 100
133 ms8260 KiB
#include <algorithm>
#include <iostream>

using namespace std;

const       int   N = 500000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long aa[N];
int bb[N], ii[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> aa[i] >> bb[i], ii[i] = i;
	sort(ii, ii + n, [] (int i, int j) { return aa[i] < aa[j]; });
	long long ans = 0, s = 0, t = -INF;
	for (int h = 0; h < n; h++) {
		int i = ii[h], b = bb[i];
		long long a = aa[i];
		t = max(t, a - s), s += b;
		ans = max(ans, s - a + t);
	}
	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...