Submission #1271645

#TimeUsernameProblemLanguageResultExecution timeMemory
1271645david_g611Art Exhibition (JOI18_art)C++20
100 / 100
412 ms19764 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int NMAX=5e5, INF=1e9*1ll*1e9;
int sz[NMAX+1], val[NMAX+1], sp[NMAX+1];

struct obiect
{
    int s, v;
    const bool operator < (const obiect &o) const{
        return s<o.s;
    }
}o[NMAX+1];

signed main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>o[i].s>>o[i].v;
    sort(o+1, o+n+1);
    for(int i=1; i<=n; i++)
    {
        sz[i]=o[i].s;
        val[i]=o[i].v;
        sp[i]=sp[i-1]+val[i];
    }
    int best=-INF;
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        best=max(best, sz[i]-sp[i-1]);
        ans=max(ans, sp[i]-sz[i]+best);
    }
    cout<<ans;
    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...