Submission #207100

# Submission time Handle Problem Language Result Execution time Memory
207100 2020-03-06T13:16:41 Z istlemin Climbers (RMI18_climbers) C++14
70 / 100
800 ms 3832 KB
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

#define rep(i, a, b) for(ll i = a; i < ll(b); ++i)
#define rrep(i, a, b) for(ll i = b-1; i >= ll(a); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;

ll n;
vi h;

ll lower(ll s){
    if(h[s]<h[s+1]) return s;
    else return s+1;
}
ll upper(ll s){
    if(h[s]<h[s+1]) return s+1;
    else return s;
}


struct Node {
    ll v,s;

    pair<ll, Node> makeEdge(ll v,Node newNode){
        return {abs(h[v]-h[newNode.v]),newNode};
    }
    
    vector<pair<ll,Node>> edges(){
        vector<pair<ll,Node>> ret;

        if(h[v+1]<h[v]){
            ll mnS = min(h[s],h[s+1]);
            if(mnS>=h[v+1])
                ret.emplace_back(makeEdge(v,Node({lower(s),v})));
            if(mnS<=h[v+1])
                ret.emplace_back(makeEdge(v,Node({v+1,s})));
            if(mnS>=h[v-1])
                ret.emplace_back(makeEdge(v,Node({lower(s),v-1})));
            if(mnS<=h[v-1])
                ret.emplace_back(makeEdge(v,Node({v-1,s})));
        } else {
            ll mxS = max(h[s],h[s+1]);
            if(mxS<=h[v+1])
                ret.emplace_back(makeEdge(v,Node({upper(s),v})));
            if(mxS>=h[v+1])
                ret.emplace_back(makeEdge(v,Node({v+1,s})));
            if(mxS<=h[v-1])
                ret.emplace_back(makeEdge(v,Node({upper(s),v-1})));
            if(mxS>=h[v-1])
                ret.emplace_back(makeEdge(v,Node({v-1,s})));
        }

        if(h[v]==h[s]) {
            ret.emplace_back(makeEdge(v,Node({s,v})));
            ret.emplace_back(makeEdge(v,Node({s,v-1})));
        }
        if(h[v]==h[s+1]) {
            ret.emplace_back(makeEdge(v,Node({s+1,v})));
            ret.emplace_back(makeEdge(v,Node({s+1,v-1})));
        }

        //cout<<v<<" "<<s<<": ";
        //trav(r,ret) cout<<"("<<r.second.v<<","<<r.second.s<<") ";
        //cout<<endl;

        return ret;
    }

    bool invalid(){
        return v==0||v==n-1||s==0||s==n-2;
    }
};

bool operator <(const Node& x, const Node& y) {
    return tie(x.v,x.s)<tie(y.v,y.s);
}


int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);

    srand(1);

    cin>>n;
    vi htemp;
    rep(i,0,n) {
        ll x;
        cin>>x;
        //x = rand()%10;
        //if(i==0||i==n-1) x = 0;
        //cout<<x<<" ";
        if(!htemp.size()||htemp.back()!=x) htemp.push_back(x);
    }
    //cout<<endl;
    h.push_back(1e9);
    h.push_back(0);
    rep(i,1,htemp.size()-1){
        if((htemp[i]<htemp[i-1])==(htemp[i]<htemp[i+1])){
            h.push_back(htemp[i]);
        }
    }
    h.push_back(0);
    h.push_back(1e9);

    //trav(hi,h) cout<<hi<<" ";
    //cout<<endl;

    n = h.size();

    set<pair<ll,Node>> q;
    vector<vector<bool>> seen(n,vector<bool>(n));
    q.emplace(0,Node({1,n-3}));
    while(q.size()){
        ll d = q.begin()->first;
        Node V = q.begin()->second;
        q.erase(q.begin());
        //cout<<d<<": "<<V.v<<" "<<V.s<<endl;
        if(seen[V.v][V.s]||V.invalid()) continue;
        seen[V.v][V.s] = true;


        if(V.v==V.s||V.v-1==V.s){
            cout<<d<<endl;
            return 0;
        }
        trav(e,V.edges()){
            q.emplace(d+e.first,e.second);
        }
    }
    assert(false);
}
# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 11 ms 504 KB Output is correct
4 Correct 32 ms 1656 KB Output is correct
5 Correct 127 ms 3832 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 438 ms 760 KB Output is correct
4 Correct 700 ms 1656 KB Output is correct
5 Execution timed out 1091 ms 1528 KB Time limit exceeded
6 Execution timed out 1022 ms 2668 KB Time limit exceeded
7 Execution timed out 1097 ms 2680 KB Time limit exceeded
8 Execution timed out 851 ms 3448 KB Time limit exceeded
9 Execution timed out 1083 ms 3576 KB Time limit exceeded
10 Execution timed out 1097 ms 3448 KB Time limit exceeded