Submission #207099

#	Time	Username	Problem	Language	Result	Execution time	Memory
207099		istlemin	Climbers (RMI18_climbers)	C++14	0 / 100	12 ms	7544 KiB

climbers

#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 false;
}


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

    cin>>n;
    vi htemp;
    rep(i,0,n) {
        ll x;
        cin>>x;
        if(!htemp.size()||htemp.back()!=x) htemp.push_back(x);
    }
    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());
        if(seen[V.v][V.s]||V.invalid()) continue;
        seen[V.v][V.s] = true;

        //cout<<d<<": "<<V.v<<" "<<V.s<<endl;

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

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50