Submission #751779

#TimeUsernameProblemLanguageResultExecution timeMemory
751779vjudge1Art Exhibition (JOI18_art)C++14
100 / 100
550 ms56076 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<ll,ll>
ll n,maxs;
pii a[500500];
ll memo[500500][3];
ll dp(ll idx, ll stat) {
	if(idx == n+1) return -1e18;
	if(memo[idx][stat] == -1) {
		memo[idx][stat] = 0;
		if(stat == 0) {
			memo[idx][stat] = max(dp(idx+1,0),dp(idx+1,1) + a[idx].se + a[idx].fi);
		}
		else if(stat == 1) {
			memo[idx][stat] = max(dp(idx+1,1)+a[idx].se, a[idx].se - a[idx].fi);
		}
	}
	return memo[idx][stat];
}
int main() {
	cin >> n;
	memset(memo,-1,sizeof(memo));
	for(int i=1; i<=n; i++) {
		cin >> a[i].fi >> a[i].se;
		maxs = max(maxs,a[i].se);
	}
	sort(a+1,a+n+1);
	cout << max(maxs,dp(1,0)) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...