Submission #310180

#	Time	Username	Problem	Language	Result	Execution time	Memory
310180		bigDuck	Climbers (RMI18_climbers)	C++14	5 / 100	343 ms	191304 KiB

climbers

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll

int t, n, m, k, h[2010], q, l, r;


struct cost{
    int ft, sc, cost;
};
vector<cost> st[2001][2001];
int d[2001][2001];


bool btwn(int p1, int p2, int p3){
return ( (h[p1]>=min(h[p2], h[p3]) )&&(h[p1]<=max(h[p2], h[p3]) )  );
}

void combine(int p1, int l1, int p2, int l2){
    if( (l1>=n) || (l2>=n) || ((min(min(l1, l2), min(p1, p2))<1) ) ){return;}
    if( (!btwn(p1, l2, l2+1)) || (!btwn(p2, l1, l1+1)) || (!btwn(p1, l1, l1+1)) || (!btwn(p2, l2, l2+1)) ){return ;}
    st[p1][l1].pb({p2, l2, abs(h[p1]-h[p2])});
    st[p2][l2].pb({p1, l1, abs(h[p1]-h[p2])} );
    return;
}



void edges(int pt, int ln){

    if(!btwn(pt, ln+1, ln)){
        return;
    }
    if(ln==n){return;}

    if(pt==n){
        if( btwn(pt-1, ln, ln+1) ){
            combine(pt-1, ln,pt, ln);
        }

        if(btwn(ln+1, pt, pt-1)){
            combine(ln+1, pt-1, pt, ln);
        }
        return;
    }

    if(pt==ln){
        if(btwn(ln+1, pt-1, pt) ){
            combine(ln+1, pt-1, pt, ln);
        }
        if(btwn(pt-1, ln, ln+1)){
            combine(pt-1, ln, pt, ln);
        }
        return;
    }

    //inainte
        //inainte
            if(btwn(pt+1, ln, ln+1)){
                combine(pt+1, ln, pt, ln);
            }
            if(btwn(ln+1, pt, pt+1)){
                combine(ln+1, pt, ln, pt);
            }
        //inapoi
            if(btwn(ln, pt, pt+1)){
                combine(ln, pt, pt, ln);
            }
            if(btwn(pt+1, ln,ln+1)){
                combine(pt+1, ln, pt, ln);
            }
    //inapoi
        //inainte
            if(btwn(pt-1, ln, ln+1)){
                combine(pt-1, ln, pt, ln);
            }
            if(btwn(ln+1, pt, pt-1)){
                combine(ln+1, pt-1, pt, ln);
            }
        //inapoi
            if(btwn(pt-1, ln, ln+1)){
                combine(pt-1, ln, pt, ln);
            }
            if(btwn(ln, pt, pt-1)){
                combine(ln, pt-1, pt, ln);
            }
return;
}


bool vr[5010][5010];
void dijkstra(){
d[n][1]=0;
multiset<pair<int, pii>> ms; ms.insert({0, {n, 1}});

while(!ms.empty()){
    auto f=*ms.begin();
    int x=f.sc.ft, y=f.sc.sc;
    d[x][y]=f.ft;
    vr[x][y]=true;
    ms.erase(ms.begin());
    edges(x, y);
    for(auto nod:st[x][y]){
        //cout<<"x"<<flush;
        int u=nod.ft, v=nod.sc, c=nod.cost;
        if(v==n){continue;}
        if(vr[u][v]==true){continue;}
        auto it=ms.find({d[u][v], {u, v}} );
        if(it!=ms.end()){ms.erase(it);}
        if(d[u][v]==-1){
            d[u][v]=d[x][y]+c;
        }
        else{
            d[u][v]=max(d[u][v], d[x][y]+c);
        }
        ms.insert({d[u][v], {u, v} } );
    }
    st[x][y].clear();
}

}







int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n; i++){
    cin>>h[i];
}

for(int x=1; x<=n; x++){
    for(int y=1; y<=n; y++){
        d[x][y]=-1;
    }
}

/*for(int x=1; x<=n; x++){
    for(int y=1; y<=n; y++){
        cout<<x<<" "<<y<<": ";
        for(auto g:st[x][y]){
            cout<<"("<<g.ft<<" "<<g.sc<<" "<<g.cost<<") ";
        }
        cout<<"\n";
    }
}*/

dijkstra();
int res=1e9;
for(int i=1; i<=n; i++){
    if(d[i][i]!=(-1)){
        res=min(res, d[i][i]);
    }
}
if(res==1e9){cout<<"NO"; return 0;}
cout<<res;



return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 5 / 25
• Subtask 3: 0 / 50