제출 #844381

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

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

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

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