Submission #237389

#TimeUsernameProblemLanguageResultExecution timeMemory
237389uacoder123Art Exhibition (JOI18_art)C++14
100 / 100
803 ms28796 KiB
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
 
int main()
{
    lli n;
    cin>>n;
    ii av[n];
    lli p[n+1],dp[n],m;
    p[0]=0;
    for(int i=0;i<n;++i)
        cin>>av[i].F>>av[i].S;
    sort(av,av+n);
    for(int i=0;i<n;++i)
        p[i+1]=p[i]+av[i].S;
    dp[n-1]=av[n-1].S;
    m=dp[n-1];
    for(int i=n-2;i>=0;--i)
    {
        dp[i]=max(av[i].S,dp[i+1]+av[i].S-av[i+1].F+av[i].F);
        m=max(m,dp[i]);
    }
    cout<<m<<endl;
    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...