oj.uz

Submission #310181

# Submission time Handle Problem Language Result Execution time Memory
310181 2020-10-06T07:20:39 Z bigDuck Climbers (RMI18_climbers) C++14
50 / 100
 800 ms 524292 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[3010], q, l, r;


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


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());
    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} } );
    }
}

}







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;
        edges(x, y);
    }
}

/*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
15.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 213112 KB Output is correct
2 Correct 152 ms 218180 KB Output is correct
3 Correct 350 ms 264428 KB Output is correct
4 Execution timed out 1127 ms 465016 KB Time limit exceeded
5 Runtime error 400 ms 428920 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 212088 KB Output is correct
2 Correct 136 ms 212600 KB Output is correct
3 Correct 144 ms 214520 KB Output is correct
4 Correct 135 ms 213368 KB Output is correct
5 Correct 174 ms 221616 KB Output is correct

Subtask #3
10.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 214140 KB Output is correct
2 Correct 177 ms 224504 KB Output is correct
3 Execution timed out 1073 ms 416760 KB Time limit exceeded
4 Execution timed out 1115 ms 524292 KB Time limit exceeded
5 Execution timed out 1126 ms 509944 KB Time limit exceeded
6 Runtime error 398 ms 429048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 398 ms 429180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 408 ms 428956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 415 ms 429180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 405 ms 428924 KB Execution killed with signal 11 (could be triggered by violating memory limits)