제출 #751108

#제출 시각아이디문제언어결과실행 시간메모리
751108vjudge1Art Exhibition (JOI18_art)C++17
100 / 100
223 ms24744 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N;

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

	cin >> N;
	vector<pair<ll, ll>> v;
	v.push_back({0, 0});
	for(int i = 0; i < N; i++) {
		ll w, x;
		cin >> w >> x;
		v.push_back({w, x});
	}
	
	sort(v.begin(), v.end());

	vector<ll> pref(N + 1);
	for(int i = 1; i <= N; i++) pref[i] = pref[i - 1] + v[i].second;
	for(int i = 0; i < N; i++) pref[i] -= v[i + 1].first;

	ll opt = pref[0], s = 0, ans = 0;
	for(int i = 1; i <= N; i++) {
		s += v[i].second;
		ans = max(ans, s - opt - v[i].first);
		opt = min(opt, pref[i]);
	}

	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...