Submission #159537

#	Time	Username	Problem	Language	Result	Execution time	Memory
159537		socho	Art Exhibition (JOI18_art)	C++14	50 / 100	1002 ms	40460 KiB

art

#include "bits/stdc++.h"
using namespace std;

int main() {
	
	long long n;
	cin >> n;
	vector<pair<long long, long long> > arr;
	for (long long i=0; i<n; i++) {
		long long sz, va;
		cin >> sz >> va;
		arr.push_back(make_pair(sz, va));
	}
	sort(arr.begin(), arr.end());
	
	long long best = 0;
	priority_queue<long long> pick;
	pick.push(arr[0].first);
	
	long long sz[n], vl[n];
	for (long long i=0; i<n; i++) sz[i] = arr[i].first;
	for (long long i=0; i<n; i++) vl[i] = arr[i].second;
	
	long long pf[n];
	pf[0] = arr[0].second;
	for (long long i=1; i<n; i++) pf[i] = pf[i-1] + vl[i];
	
	for (long long right=0; right<n; right++) {
		long long cons = pf[right] - sz[right];
		// maximise the other
		if (right > 0) {
			pick.push(-pf[right-1]+sz[right]);
		}
		best = max(best, cons + pick.top());
	}
	
	cout << best << endl;
   
}

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