Submission #75848

#	Time	Username	Problem	Language	Result	Execution time	Memory
75848		Vasiljko	Art Exhibition (JOI18_art)	C++14	100 / 100	448 ms	93924 KiB

art

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;
const int N = 5e5+5;

ll a[N],p[N];
int n;
set<ll>s;

struct art{
    ll A,B;
    bool operator < (const art &rhs) const{
        return A<rhs.A;
    }
}d[N];

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>d[i].A>>d[i].B;

    sort(d+1,d+1+n);

    s.insert(-d[1].A);
    ll ans=-1;
    for(int i=1;i<=n;i++){
        ans=max(ans,d[i].B);
        p[i]=p[i-1]+d[i].B;
    }

    for(int i=2;i<=n;i++){
        ll val=*(s.begin());
        ans=max(ans,p[i]-d[i].A-val);
        s.insert(p[i-1]-d[i].A);
    }
    cout<<ans;
    return 0;
}

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