제출 #707374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707374		NourWael	Art Exhibition (JOI18_art)	C++14	0 / 100	1 ms	212 KiB

art

#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

vector<pair<ll,ll>>v;
int n;

ll dp[500005][3];

ll art(int i, int k)
{
    if(k==2)
    return 0;

    if (i==n && k==1)
        return -v[i].first;

    if(i==n && k==0)
        return 0;

    if(dp[i][k]!=-1e18)
        return dp[i][k];

    ll a=-1e18;

    if(k==0)
    {
       a=max(a,art(i+1,1)+v[i].second+v[i].first);
       a=max(a,art(i+1,0));
       a=max(a,art(i+1,2)-v[i].first);
    }
    else if(k==1)
    {
        a=max(a,art(i+1,1)+v[i].second);
        a=max(a,art(i+1,2)+v[i].second-v[i].first);
    }

    dp[i][k]=a;
    return a;
}

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



    cin>>n;
    v.resize(n);

    for(int i=0;i<n;i++)
    {
        cin>>v[i].first>>v[i].second;

    }
    sort(v.begin(),v.end());

    for(int i=0;i<n;i++)
        for(int j=0;j<3;j++)
            dp[i][j]=-1e18;

    cout<<art(0,0);


    return 0;
}

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