Submission #642212

#	Time	Username	Problem	Language	Result	Execution time	Memory
642212		as111	Art Exhibition (JOI18_art)	C++14	0 / 100	1 ms	212 KiB

art

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

	cout << endl;
	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;
}

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