제출 #75848

#제출 시각아이디문제언어결과실행 시간메모리
75848VasiljkoArt Exhibition (JOI18_art)C++14
100 / 100
448 ms93924 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...