Submission #231017

#	Time	Username	Problem	Language	Result	Execution time	Memory
231017		peijar	Art Exhibition (JOI18_art)	C++17	100 / 100	239 ms	28792 KiB

art

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

#define SZ(v) ((int)(v).size())
using ll = long long;

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nb_pieces;
	cin >> nb_pieces;
	vector<pair<ll, ll> > pieces(nb_pieces);
	for (auto &[taille, valeur] : pieces)
		cin >> taille >> valeur;

	sort(pieces.begin(), pieces.end());

	vector<ll> prefix_sum(nb_pieces+1);
	for (int i(0); i < nb_pieces; ++i)
		prefix_sum[i+1] = prefix_sum[i] + pieces[i].second;
	vector<ll> suffix_max(nb_pieces+1);
	suffix_max[nb_pieces] = -1e18;
	for (int i(nb_pieces-1); i >= 0; --i)
		suffix_max[i] = max(suffix_max[i+1], prefix_sum[i+1] - pieces[i].first);

	ll ans(-1e18);
	for (int i(0); i < nb_pieces; ++i)
		ans = max(ans, pieces[i].first + suffix_max[i] - prefix_sum[i]);
	cout << ans << endl;
}

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