제출 #255821

#제출 시각아이디문제언어결과실행 시간메모리
255821shrek12357Art Exhibition (JOI18_art)C++14
100 / 100
899 ms32596 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<pair<long long, long long>> art;
	for (int i = 0; i < n; i++) {
		long long a, b;
		cin >> a >> b;
		art.push_back(make_pair(a, b));
	}
	sort(art.begin(), art.end());
	vector<long long> pre(n + 1);
	pre[0] = 0;
	vector<long long> diff(n + 1);
	diff[0] = 0;
	for (int i = 0; i < n; i++) {
		pre[i + 1] = pre[i] + art[i].second;
		diff[i + 1] = pre[i + 1] - art[i].first;
	}
	vector<long long> maxes(n + 1);
	for (int i = n; i > 0; i--) {
		if (i == n) {
			maxes[i] = diff[i];
		}
		else {
			maxes[i] = max(maxes[i + 1], diff[i]);
		}
	}
	maxes[0] = 0;
	long long best = 0;
	for (int i = 1; i <= n; i++) {
		long long cur = art[i - 1].first;
		cur += maxes[i] - pre[i - 1];
		best = max(best, cur);
	}
	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...