Submission #330384

#	Time	Username	Problem	Language	Result	Execution time	Memory
330384		Seanliu	Art Exhibition (JOI18_art)	C++14	100 / 100	225 ms	8428 KiB

art

#include <iostream>
#include <algorithm>
#include <utility>
#define pii pair<int,int>
#define F first
#define S second
#define int long long int
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
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(){
	ericxiao;
	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;
}

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