제출 #330383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330383		Seanliu	Art Exhibition (JOI18_art)	C++14	100 / 100	564 ms	21020 KiB

art

#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;
}

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