제출 #159538

#제출 시각아이디문제언어결과실행 시간메모리
159538sochoArt Exhibition (JOI18_art)C++14
100 / 100
318 ms40704 KiB
#include "bits/stdc++.h"
using namespace std;

int main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  
	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;
   
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...