Submission #844535

#	Time	Username	Problem	Language	Result	Execution time	Memory
844535		Mr_Husanboy	Art Exhibition (JOI18_art)	C++17	100 / 100	157 ms	30828 KiB

art

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()

template<typename T>
int len(T &a){return a.size();}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;

	vector<ll> a(n), b(n);

	for(int i = 0; i < n; i ++){
		cin >> a[i] >> b[i];
	}

	vector<int> p(n); iota(all(p),0);

	sort(all(p), [&](int i, int j){return a[i] < a[j];});

	vector<ll> val(n);
	ll cur = 0;
	for(int i = 0; i < n; i ++){
		cur += b[p[i]];
		if(i > 0) cur -= a[p[i]] - a[p[i - 1]];
		val[i] = cur;
	}

	vector<ll> mx(n);
	mx[n - 1] = val[n - 1];
	for(int i = n - 2; i >= 0; i --){
		mx[i] = max(val[i], mx[i + 1]);
	}
	
	

	ll ans = 0; cur = 0;

	for(int i = 0; i < n; i ++){
		ans = max(ans, mx[i] - cur);
		cur += b[p[i]];
		if(i < n - 1) cur -= a[p[i + 1]] - a[p[i]];
	}

	cout << ans;
	return 0;
}

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