제출 #687682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
687682		NK_	Art Exhibition (JOI18_art)	C++17	100 / 100	242 ms	28648 KiB

art

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

using namespace std;

#define nl '\n'

using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	vector<ll> A(N); vector<int> B(N);
	for(int i = 0; i < N; i++) cin >> A[i] >> B[i];

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

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

	for(int i = 1; i < N; i++) P[i] += P[i-1];

	ll ans = 0, S = 0;
	

	vector<ll> mx = P; for(int i = N-2; i >= 0; i--) mx[i] = max(mx[i], mx[i+1]);

	for(int i = 0; i < N; i++) {
		ll res = mx[i] - S + A[I[i]]; S += B[I[i]];
		ans = max(ans, res);
	}

	cout << ans << nl;


    return 0;
}

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