Submission #642213

#TimeUsernameProblemLanguageResultExecution timeMemory
642213as111Art Exhibition (JOI18_art)C++14
0 / 100
0 ms212 KiB
#include <iostream>
#include <vector>
#include <algorithm>

#define MAXN 500000

using namespace std;
bool sortcol(vector<int> v1, vector<int> v2) {
	return v1[0] < v2[0];
}
vector< vector<int> > vect;
int pre[MAXN];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int A, B;
		cin >> A >> B;
		vector<int> vals;
		vals.push_back(A); vals.push_back(B);
		vect.push_back(vals);
	}
	sort(vect.begin(), vect.end(), sortcol);
	
	int 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;
	int 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...