Submission #1271645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271645		david_g611	Art Exhibition (JOI18_art)	C++20	100 / 100	412 ms	19764 KiB

art

#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;
}

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