제출 #757066

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