Submission #459659

#	Time	Username	Problem	Language	Result	Execution time	Memory
459659		Hamed5001	Art Exhibition (JOI18_art)	C++14	100 / 100	294 ms	21360 KiB

art

#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();
}

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