Submission #1273640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273640		kaiboy	Art Exhibition (JOI18_art)	C++20	100 / 100	133 ms	8260 KiB

art

#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;
}

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