Submission #1115274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115274		staszic_ojuz	Art Exhibition (JOI18_art)	C++17	100 / 100	153 ms	22856 KiB

art

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

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