Submission #79985

#	Time	Username	Problem	Language	Result	Execution time	Memory
79985		Genezio	Art Exhibition (JOI18_art)	C++14	100 / 100	321 ms	254888 KiB

art

#include<bits/stdc++.h>

using namespace std;

const int N = 500010;

#define ll long long int
#define F first
#define S second

pair<ll,ll> v[N];
ll dp[N][2];
int n;

ll f(int x,int y) {
	if(dp[x][y]>=0) return dp[x][y];
	ll aux = v[x].S-v[x].F+v[x-1].F;
	if(y) {
		if(x==n) return aux;
		return dp[x][y]=max(aux,aux+f(x+1,y));
	} else {
		if(x==n) return v[x].S;
		return dp[x][y]=max({v[x].S,f(x+1,y),v[x].S+f(x+1,y+1)});
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>v[i].F>>v[i].S;
	}
	sort(v+1,v+n+1);
	memset(dp,-1,sizeof(dp));
	cout<<f(1,0)<<"\n";
}

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