Submission #819624

#	Time	Username	Problem	Language	Result	Execution time	Memory
819624		jokhara	Art Exhibition (JOI18_art)	C++14	0 / 100	0 ms	212 KiB

art

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

vector<pair<int,int> > art;
int pval[500010];

bool cmp(pair<int,int>a,pair<int,int>b){
    return a.fi<b.fi;
}

int main(){
    int n; cin>>n;
    int size,val;
    for(int i=0;i<n;i++){
        cin>>size>>val;
        art.push_back(make_pair(size,val));
    }
    sort(art.begin(),art.end(),cmp);
    pval[0]=art[0].se;
    for(int i=1;i<n;i++){
        pval[i]=pval[i-1]+art[i].se;
    }
    int plevi=0;
    int mai=0;
    for(int i=0;i<n;i++){
        if(art[i].fi-art[0].fi-pval[i-1]>mai){
            mai=art[i].fi-art[0].fi-pval[i-1];
            plevi=i;
        }
    }
    int pdesni=n-1;
    int prom=0;
    for(int i=n-1;i>=0;i--){
        if(art[n-1].fi-art[i].fi-pval[n-1]+pval[i]>prom){
            prom=art[n-1].fi-art[i].fi-pval[n-1]+pval[i];
            pdesni=i;
        }
    }
    //cerr<<plevi<<" "<<pdesni<<"\n";
    if(pdesni>=plevi){
        if(plevi==0) cout<<pval[pdesni]-art[pdesni].fi+art[plevi].fi;
        else cout<<pval[pdesni]-pval[plevi-1]-art[pdesni].fi+art[plevi].fi;
    }else{
        int plevi2=0;
        int mai2=0;
        for(int i=0;i<=pdesni;i++){
            if(art[i].fi-art[0].fi-pval[i]>mai2){
                mai2=art[i].fi-art[0].fi-pval[i-1];
                plevi2=i;
            }
        }
        int pdesni2=n-1;
        int prom2=0;
        for(int i=n-1;i>=plevi;i--){
            if(art[n-1].fi-art[i].fi-pval[n-1]+pval[i]>prom2){
                prom2=art[n-1].fi-art[i].fi-pval[n-1]+pval[i];
                pdesni2=i;
            }
        }
        cout<<max(pval[pdesni]-pval[plevi2-1>=0?plevi2-1:500009]+art[plevi2].fi-art[pdesni].fi,pval[pdesni2]-pval[plevi-1>0?plevi-1:500009]+art[plevi].fi-art[pdesni2].fi);
    }
    return 0;
}

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