Submission #757066

#	Time	Username	Problem	Language	Result	Execution time	Memory
757066		siewjh	Art Exhibition (JOI18_art)	C++17	100 / 100	433 ms	48308 KiB

art

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums; cin >> nums;
	vector<pair<ll, ll>> vec(nums + 1);
	for (int i = 1; i <= nums; i++){
		ll s, v; cin >> s >> v;
		vec[i] = {s, v};
	}
	sort(vec.begin() + 1, vec.end());
	vector<ll> pref(nums + 1);
	multiset<ll> s;
	pref[0] = 0;
	for (int i = 1; i <= nums; i++){
		pref[i] = pref[i - 1] + vec[i].second;
		s.insert(pref[i] - vec[i].first);
	}
	ll ans = 0;
	for (int i = 1; i <= nums; i++){
		ans = max(ans, *s.rbegin() - pref[i - 1] + vec[i].first);
		s.erase(s.find(pref[i] - vec[i].first));
	}
	cout << ans;
}

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