Submission #464580

#	Time	Username	Problem	Language	Result	Execution time	Memory
464580		Sarah_Mokhtar	Art Exhibition (JOI18_art)	C++14	100 / 100	824 ms	52204 KiB

art

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

}

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