oj.uz

Submission #819624

# Submission time Handle Problem Language Result Execution time Memory
819624 2023-08-10T12:12:51 Z jokhara Art Exhibition (JOI18_art) C++14
0 / 100
 0 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -