제출 #381547

#제출 시각아이디문제언어결과실행 시간메모리
381547BlancaHMArt Exhibition (JOI18_art)C++14
100 / 100
230 ms28908 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

int N;
vector<pair<ll, ll>> artworks;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	artworks = vector<pair<ll, ll>>(N);
	for (int i = 0; i < N; i++)
		cin >> artworks[i].first >> artworks[i].second;
	sort(artworks.begin(), artworks.end());
	vector <ll> cum(N);
	cum[0] = artworks[0].second;
	for (int i = 1; i < N; i++)
		cum[i] = cum[i-1] + artworks[i].second;
	ll maxSum[N];
	maxSum[N-1] = cum[N-1] - artworks[N-1].first;
	for (int i = N-2; i >= 0; i--)
		maxSum[i] = max(cum[i] - artworks[i].first, maxSum[i+1]);
	ll record = max(artworks[0].second, maxSum[0] + artworks[0].first);
	for (int i = 1; i < N; i++)
		record = max(record, max(artworks[i].second, maxSum[i] + artworks[i].first - cum[i-1]));
	cout << record << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...