제출 #231017

#제출 시각아이디문제언어결과실행 시간메모리
231017peijarArt Exhibition (JOI18_art)C++17
100 / 100
239 ms28792 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...