Submission #86848

#	Time	Username	Problem	Language	Result	Execution time	Memory
86848		KCSC	Art Exhibition (JOI18_art)	C++14	100 / 100	691 ms	68556 KiB

art

#include <bits/stdc++.h>
using namespace std;

// psm[i] - psm[j - 1] - (arr[i] - arr[j])
// psm[i] - arr[i] - (-arr[j] + psm[j - 1])

const int DIM = 500005;

pair<long long, long long> arr[DIM];

int main(void) {
#ifdef HOME
	freopen("art.in", "r", stdin);
	freopen("art.out", "w", stdout);
#endif
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i].first >> arr[i].second; }
	sort(arr + 1, arr + n + 1);
	long long mn = 1LL << 60, mx = -1LL << 60;
	for (int i = 1; i <= n; ++i) {
		arr[i].second += arr[i - 1].second;
		mn = min(mn, -arr[i].first + arr[i - 1].second);
		mx = max(mx, arr[i].second - arr[i].first - mn); }
	cout << mx;
	return 0; }

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