Submission #912432

#	Time	Username	Problem	Language	Result	Execution time	Memory
912432		NK_	Art Exhibition (JOI18_art)	C++17	100 / 100	186 ms	28908 KiB

art

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;

const ll INFL = 2e18;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	vl A(N), B(N); for(int i = 0; i < N; i++) cin >> A[i] >> B[i];

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

	vl P = {0}; for(auto& i : ord) P.pb(P.back() + B[i]);

	ll ans = 0, mn = INFL;

	for(int i = 0; i <= N; i++) {
		if (i != 0) {
			ans = max(P[i] - A[ord[i - 1]] - mn, ans);
		}

		if (i != N) mn = min(P[i] - A[ord[i]], mn);
	}

	cout << ans << nl;
	exit(0-0);
}	

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