Submission #66734

#	Time	Username	Problem	Language	Result	Execution time	Memory
66734		cdemirer	Art Exhibition (JOI18_art)	C++17	100 / 100	387 ms	20468 KiB

art

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vi> vvi;
typedef pair<double, double> dodo;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int N;
ll A[500000], B[500000];
ll opt[500000];

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) cin >> B[i] >> A[i];
	vector<pair<ll, ll> > tmp;
	for (int i = 0; i < N; i++) tmp.pb(mp(B[i], A[i]));
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < N; i++) A[i] = tmp[i].second, B[i] = tmp[i].first;
	
	opt[N-1] = A[N-1];
	for (int i = N-2; i >= 0; i--) {
		opt[i] = A[i];
		ll delta = opt[i+1] - (B[i+1] - B[i]);
		if (delta > 0) opt[i] += delta;
	}
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		ans = max(ans, opt[i]);
	}
	cout << ans << endl;
	
	return 0;
}

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