Submission #459659

#TimeUsernameProblemLanguageResultExecution timeMemory
459659Hamed5001Art Exhibition (JOI18_art)C++14
100 / 100
294 ms21360 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
	int N;
	cin >> N;

	pair<ll, ll> A[N+1];
	A[0].first = A[0].second = 0;

	for (int i = 1; i <= N; i++)
		cin >> A[i].first >> A[i].second;

	sort(A+1, A+N+1);

	ll CUM[N+1];
	CUM[0] = 0;

	for (int i = 1; i <= N; i++)
		CUM[i] = CUM[i-1] + A[i].second;

    priority_queue<pair<ll, int>> pq;
    ll S = 0;
    for (int i = 1; i <= N; i++) {
    	S += A[i].second - A[i].first + A[i-1].first;
    	pq.push({S, i});
    }

    ll ans = 0;
    
    for (int i = 1; i <= N; i++) {
    	while(pq.top().second < i) pq.pop();
    	if (pq.size()) ans = max(ans, CUM[pq.top().second] - CUM[i-1] + A[i].first - A[pq.top().second].first);
    }

	cout << ans;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...