Submission #330383

#TimeUsernameProblemLanguageResultExecution timeMemory
330383SeanliuArt Exhibition (JOI18_art)C++14
100 / 100
564 ms21020 KiB
#include <iostream>
#include <algorithm>
#include <utility>
#define pii pair<int,int>
#define F first
#define S second
#define int long long int
using namespace std;
const int maxN = 5e5 + 326;
pii vals[maxN];

int N, ans, maxVal;

//(vals[r].S - vals[l - 1].S) - (vals[r].F - vals[l].F)
//(vals[r].S - vals[r].F) + (vals[l].F - vals[l - 1].S)

signed main(){
	cin >> N;
	for(int i = 1; i <= N; i++) cin >> vals[i].F >> vals[i].S;
	sort(vals + 1, vals + N + 1);
	for(int i = 1; i <= N; i++) vals[i].S += vals[i - 1].S;
	ans = vals[N].S - vals[N - 1].S;
	maxVal = vals[N].S - vals[N].F;
	for(int i = N - 1; i; i--){
		ans = max(ans, maxVal + vals[i].F - vals[i - 1].S);  	
		ans = max(ans, vals[i].S - vals[i - 1].S);
		maxVal = max(maxVal, vals[i].S - vals[i].F);
	}
	cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...