Submission #752101

#	Time	Username	Problem	Language	Result	Execution time	Memory
752101		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	218 ms	61332 KiB

art

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pii pair<ll,ll>
#define piii pair<int, pair<int, int>
#define v(int) vector<int>
#define si size()
#define foe(i,a,b) for(int i=a;i<=b;++i)
#define fol(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define Bit(mask,i) (1<<i)&mask
#define offBit(mask,i) (1<<i)^mask
#define onBit(mask,i) (1<<i)mask
#define CNT(x) __builtin_popcountll(x)
const ll int mod = 1e9+7;
const ll int base = 2309;
const ll int inf = 1e18;
const int N = 500500;
const int LG = 20;
// ▄  ▄ ▄  ▄ ▄  ▄ ▄  ▄ ▄  ▄ ▄▄ ▄ ▄▄▄▄
// █▄▄█ █  █ █  █ █▄▄█ █  █ ██ █ █ ▄▄
// █  █ █▄▄█ █▄▄█ █  █ █▄▄█ █ ██ █▄▄█

ll n,maxx;
pii a[N];
ll nho[N][3];
ll dp(ll idx, ll tk)
{
	if(idx == n+1)
        return -inf;
	if(nho[idx][tk] == -1)
	{
		nho[idx][tk] = 0;
		if(tk == 0)
		{
			nho[idx][tk] = max(dp(idx+1,0),dp(idx+1,1) + a[idx].se + a[idx].fi);
		}
		else if(tk == 1)
		{
			nho[idx][tk] = max(dp(idx+1,1)+a[idx].se, a[idx].se - a[idx].fi);
		}
	}
	return nho[idx][tk];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin >> n;
	memset(nho,-1,sizeof(nho));
	for(int i=1; i<=n; i++)
    {
		cin >> a[i].fi >> a[i].se;
		maxx = max(maxx,a[i].se);
	}
	sort(a+1,a+n+1);
	cout << max(maxx,dp(1,0)) << endl;
}

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