Submission #642214

#	Time	Username	Problem	Language	Result	Execution time	Memory
642214		as111	Art Exhibition (JOI18_art)	C++14	50 / 100	1088 ms	40304 KiB

art

#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() {
	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;
}

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