Submission #86848

#TimeUsernameProblemLanguageResultExecution timeMemory
86848KCSCArt Exhibition (JOI18_art)C++14
100 / 100
691 ms68556 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...