Submission #1255101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255101		ciao_gio	Art Exhibition (JOI18_art)	C++20	100 / 100	384 ms	18036 KiB

art

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

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