oj.uz

Submission #310180

# Submission time Handle Problem Language Result Execution time Memory
310180 2020-10-06T07:16:28 Z bigDuck Climbers (RMI18_climbers) C++14
5 / 100
 343 ms 191304 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 94840 KB Output isn't correct
2 Incorrect 61 ms 95976 KB Output isn't correct
3 Incorrect 65 ms 102268 KB Output isn't correct
4 Runtime error 178 ms 190912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 178 ms 191096 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94700 KB Output is correct
2 Incorrect 60 ms 94712 KB Output isn't correct
3 Incorrect 61 ms 95228 KB Output isn't correct
4 Incorrect 60 ms 94840 KB Output isn't correct
5 Incorrect 61 ms 96760 KB Output isn't correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 95116 KB Output isn't correct
2 Incorrect 62 ms 95992 KB Output isn't correct
3 Incorrect 343 ms 138488 KB Output isn't correct
4 Runtime error 181 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 182 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 182 ms 191304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 183 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 184 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 183 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 181 ms 191096 KB Execution killed with signal 11 (could be triggered by violating memory limits)