제출 #642215

#제출 시각아이디문제언어결과실행 시간메모리
642215as111Art Exhibition (JOI18_art)C++14
100 / 100
911 ms44368 KiB
#include <iostream>
#include <vector>
#include <algorithm>

#define MAXN 500000

using namespace std;
bool sortcol(vector<long long> v1, vector<long long> v2) {
	return v1[0] < v2[0];
}
vector< vector<long long> > vect;
long long pre[MAXN];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		long long A, B;
		cin >> A >> B;
		vector<long long> vals;
		vals.push_back(A); vals.push_back(B);
		vect.push_back(vals);
	}
	sort(vect.begin(), vect.end(), sortcol);
	
	long long curr = 0;
	for (int i = 0; i < N-1; i++) {
		curr = max(curr, vect[i][1]);
		pre[i] = curr;
		curr += (vect[i][0] - vect[i+1][0] + vect[i+1][1]);
	}
	pre[N - 1] = max(curr, vect[N - 1][1]);
	curr = 0;
	long long ans = 0;
	for (int i = N-1; i >0; i--) {
		curr = max(curr, vect[i][1]);
		ans = max(ans, pre[i] + curr - vect[i][1]);
		curr += (vect[i-1][0] - vect[i][0] + vect[i-1][1]);
	}
	ans = max(ans, vect[0][1]);
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...