Submission #751779

#	Time	Username	Problem	Language	Result	Execution time	Memory
751779		vjudge1	Art Exhibition (JOI18_art)	C++14	100 / 100	550 ms	56076 KiB

art

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

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