Submission #801739

#	Time	Username	Problem	Language	Result	Execution time	Memory
801739		jansenkenpegrasio	Art Exhibition (JOI18_art)	C++14	100 / 100	184 ms	24684 KiB

art

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define fi first
#define se second
#define pb push_back
#define pq priority_queue
#define mp make_pair
#define all(x) x.begin(), x.end()
#define Repp(i, l, r, a) for (int i = l; i < r; i += a)
#define Rep(i, l, r) Repp(i, l, r, 1)
#define For(i, n) Rep(i, 0, n)
#define Fori(i, n) Rep(i, 1, n + 1)
#define Each(x, v) for (auto x : v)
#define Repd(i, l, r) for (int i = r - 1; i >= l; i--)
#define Ford(i, n) Repd(i, 0, n)
#define endl "\n"

const ll INF = 1e18;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N; cin >> N;
	pll data[N + 1];
	Fori (i, N) cin >> data[i].fi >> data[i].se;
	sort(data + 1, data + N + 1);
	
//	cout << "data" << endl;
//	Fori (i, N) cout << "(" << data[i].fi << " " << data[i].se << ")" << endl;
//	cout << endl;
	
	ll pref[N + 1];
	pref[0] = 0;
	Fori (i, N) pref[i] = pref[i - 1] + data[i].se;
	
//	for (int i = 0; i <= N; i++) cout << pref[i] << " "; cout << endl;
	
	ll ans = -INF, niki = INF;
	Fori (i, N) {
		niki = min(niki, -data[i].fi + pref[i - 1]);
		ans = max(ans, -data[i].fi + pref[i] - niki);
//		cout << i << ": niki " << niki << " ans " << ans << endl;
	}
	cout << ans << endl;
	return 0;
}

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