Submission #819747

#	Time	Username	Problem	Language	Result	Execution time	Memory
819747		jokhara	Art Exhibition (JOI18_art)	C++14	0 / 100	1 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;
    for(int i=0;i<n;i++){
        int size,val; cin>>size>>val;
        art.push_back(make_pair(size,val));
    }
    sort(art.begin(),art.end(),cmp);
    //for(int i=0;i<n;i++) cerr<<art[i].fi<<" "<<art[i].se<<"\n";
    //cerr<<"\n\n\n";
    pval[0]=art[0].se;
    for(int i=1;i<n;i++) pval[i]=pval[i-1]+art[i].se;
    /*for(int i=0;i<n;i++) cerr<<pval[i]<<"\n";
    cerr<<"\n\n\n";*/
    int pi=0;
    int pom=0;
    for(int i=1;i<n;i++){
        //cerr<<art[i].fi-art[0].fi-pval[i-1]<<"\n";
        if(art[i].fi-art[0].fi-pval[i-1]>pom){
            pom=art[i].fi-art[0].fi-pval[i-1];
            pi=i;
        }
    }
    //cerr<<"\n\n\n";
    int di=n-1;
    pom=0;
    for(int i=n-1;i>=0;i--){
        //cerr<<art[n-1].fi-art[i].fi-pval[n-1]+pval[i]<<"\n";
        if(art[n-1].fi-art[i].fi-pval[n-1]+pval[i]>pom){
            pom=art[n-1].fi-art[i].fi-pval[n-1]+pval[i];
            di=i;
        }
    }
    //cerr<<"\n\n\n";
    //cerr<<di<<" "<<pi<<"\n";
    cout<<pval[di]-pval[pi>0?pi-1:500009]-art[di].fi+art[pi].fi;
    return 0;
}


/*
5
1 1
2 1
3 11
5 5
6 6
*/

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