oj.uz

Submission #310179

# Submission time Handle Problem Language Result Execution time Memory
310179 2020-10-06T07:11:59 Z bigDuck Climbers (RMI18_climbers) C++14
50 / 100
 800 ms 299692 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());
    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 63 ms 95608 KB Output is correct
2 Correct 78 ms 100856 KB Output is correct
3 Correct 280 ms 146936 KB Output is correct
4 Runtime error 185 ms 190972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 181 ms 190968 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 61 ms 94712 KB Output is correct
2 Correct 61 ms 95096 KB Output is correct
3 Correct 68 ms 97016 KB Output is correct
4 Correct 65 ms 95864 KB Output is correct
5 Correct 96 ms 104184 KB Output is correct

Subtask #3
10.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 96632 KB Output is correct
2 Correct 104 ms 107128 KB Output is correct
3 Execution timed out 1116 ms 299692 KB Time limit exceeded
4 Runtime error 180 ms 191096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 176 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 181 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 180 ms 191224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 180 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 179 ms 191100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 182 ms 190968 KB Execution killed with signal 11 (could be triggered by violating memory limits)