Submission #268674

#	Time	Username	Problem	Language	Result	Execution time	Memory
268674		Mounir	Art Exhibition (JOI18_art)	C++14	100 / 100	223 ms	24824 KiB

art

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define sz(v) (int)v.size()
#define pb push_back
#define int long long
using namespace std;

struct Oeuvre {
	int val, taille;
	
	bool operator < (const Oeuvre &autre) const {
		if (taille != autre.taille)
			return taille > autre.taille;
		return val < autre.val;
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int nOeuvres;
	cin >> nOeuvres;
	
	vector<Oeuvre> oeuvres(nOeuvres);
	for (Oeuvre& oeuvre : oeuvres)
		cin >> oeuvre.taille >> oeuvre.val;
	
	sort(all(oeuvres));
	vector<int> cum(nOeuvres, 0);
	for (int ind = 1; ind < nOeuvres; ++ind)
		cum[ind] = cum[ind - 1] + oeuvres[ind].val;
	
	int maxi = 0, mini = 1e15;
	for (int fin = 0; fin < nOeuvres; ++fin){
		int S = cum[fin] + oeuvres[fin].taille;
		chmin(mini, S - oeuvres[fin].val);
		chmax(maxi, S - mini);
	//	cout << maxi << " " << S << " " << mini << endl;
	}
	cout << maxi << endl;
	return 0;
}

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