Submission #1229114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229114		ngu	Art Exhibition (JOI18_art)	C++20	100 / 100	106 ms	12112 KiB

art

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int const MOD = 1e9 + 7, N = 5e5 + 5;

int n, val[N];

pair<int, int> a[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
	sort(a + 1, a + n + 1);
	int ma = -1e18, res = -1e18;
	for(int i = 1; i <= n; i++){
		val[i] = val[i - 1] + a[i].se;
		ma = max(ma, a[i].fi - val[i - 1]);
		res = max(res, ma + val[i] - a[i].fi);
	}
	// (val[r] - val[l - 1]) - a[r].fi + a[l].fi;
	// (val[r] - a[r].fi) + (a[l].fi - val[l - 1]);
	/*
	for(int i = 1; i <= n; i ++) {
	}*/
	cout << res;
}

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