Submission #381547

#	Time	Username	Problem	Language	Result	Execution time	Memory
381547		BlancaHM	Art Exhibition (JOI18_art)	C++14	100 / 100	230 ms	28908 KiB

art

#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;
}

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