Submission #1229015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229015		ngu	Art Exhibition (JOI18_art)	C++20	100 / 100	109 ms	12116 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], luu[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);
	val[1] = a[1].se;
	luu[1] = val[1] - a[1].fi;
	for(int i = 2; i <= n; i++){
		val[i] = val[i - 1] + a[i].se;
		//luu[i] = val[i] - a[i].fi;
	}
	//sort(luu + 1, luu + n + 1);
	//cout << luu[n] + luu[n - 1];
	// (val[r] - val[l - 1]) - a[r].fi + a[l].fi
	// (val[r] - a[r].fi) + (a[l].fi - val[l - 1])
	
	int ma = -1e18, res = -1e18;
	for(int i = 1; i <= n; i ++) {
		ma = max(ma, a[i].fi - val[i - 1]);
		res = max(res, ma + val[i] - a[i].fi);
	}
	cout << res;
}

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