제출 #79985

#제출 시각아이디문제언어결과실행 시간메모리
79985GenezioArt Exhibition (JOI18_art)C++14
100 / 100
321 ms254888 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...