제출 #844378

#제출 시각아이디문제언어결과실행 시간메모리
844378Mr_HusanboyArt Exhibition (JOI18_art)C++17
50 / 100
1028 ms13904 KiB
#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 ans = 0;
	for(int j = 0; j < n; j ++){

		ll cur = 0;
		for(int i = j; i < n; i ++){
			cur += b[p[i]];
			ans = max(ans, cur - (a[p[i]] - a[p[j]]));
		}
	}
	cout << ans << '\n'; return 0;
	// 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;

	// for(int i = 0; i < n; i ++){
	// 	ans = max(ans, mx[i] - (i > 0 ? val[i] : 0));
	// }
	// cout << ans << '\n';
	// return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...