oj.uz

Submission #310178

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


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


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 17 ms 25088 KB Output is correct
2 Correct 33 ms 29824 KB Output is correct
3 Correct 234 ms 72440 KB Output is correct
4 Runtime error 47 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 48 ms 48120 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 18 ms 24184 KB Output is correct
2 Correct 17 ms 24704 KB Output is correct
3 Correct 24 ms 26368 KB Output is correct
4 Correct 20 ms 25344 KB Output is correct
5 Correct 53 ms 33016 KB Output is correct

Subtask #3
10.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 26112 KB Output is correct
2 Correct 57 ms 36216 KB Output is correct
3 Execution timed out 1101 ms 225484 KB Time limit exceeded
4 Runtime error 47 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 47 ms 48168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 47 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 50 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 48 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 47 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 48 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)