제출 #464580

#제출 시각아이디문제언어결과실행 시간메모리
464580Sarah_MokhtarArt Exhibition (JOI18_art)C++14
100 / 100
824 ms52204 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define read freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#define LESSGO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll N=1e6+10,M=505,OO=1e16,mod=1e9+7;
int n;
ll ans,pref[N],v[N];
pair<ll,ll>a[N];
int main(){
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i].first>>a[i].second;
    }
    sort(a,a+n);
    pref[0]=a[0].second;
    for(int i=1;i<n;++i){
        pref[i]=pref[i-1]+a[i].second;
    }
    set<ll>s;
    for(int i=0;i<n;++i){
        s.insert(pref[i]-a[i].first);
        v[i]=pref[i]-a[i].first;
    }
    for(int i=0;i<n;++i){
        ll cur=(i?pref[i-1]:0)-a[i].first;
        if(s.empty()) continue;
        auto it=--(s.end());
        cur=*it-cur;
        ans=max(ans,cur);
        auto f=s.find(pref[i]-a[i].first);
        if(f==s.end()) continue;
        s.erase(f);
    }
    cout<<ans<<'\n';

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...