Submission #707376

#TimeUsernameProblemLanguageResultExecution timeMemory
707376NourWaelArt Exhibition (JOI18_art)C++14
100 / 100
240 ms63836 KiB
#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-1].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].second);
    }
    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...