Submission #1115274

#TimeUsernameProblemLanguageResultExecution timeMemory
1115274staszic_ojuzArt Exhibition (JOI18_art)C++17
100 / 100
153 ms22856 KiB
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 500003;

int n;

pair<ll, ll> val[MAXN];

ll pref_b[MAXN];
ll max_pref_b[MAXN];

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

	for (int i = 1; n >= i; i++) {
		cin >> val[i].first >> val[i].second;
	}
	
	sort(val + 1, val + n + 1);
	
	for (int i = 1; n >= i; i++) {
		pref_b[i] = pref_b[i - 1] + val[i].second;
	}
	
	for (int i = 1; n >= i; i++) {
		max_pref_b[i] = max(max_pref_b[i - 1], val[i].first - pref_b[i - 1]);
	}
	
	ll wynik= 0;
	
	for (int i = 1; n >= i; i++) {
		wynik = max(wynik, pref_b[i] - val[i].first + max_pref_b[i]);
	}
	
	cout << wynik;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...