oj.uz

답안 #207102

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207102 2020-03-06T13:19:51 Z istlemin Climbers (RMI18_climbers) C++14
95 / 100
 800 ms 3704 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();

    priority_queue<pair<ll,Node>,vector<pair<ll,Node>>,greater<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.top().first;
        Node V = q.top().second;
        q.pop();
        //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()){
            if(seen[e.second.v][e.second.s]||e.second.invalid()) continue;
            q.emplace(d+e.first,e.second);
        }
    }
    assert(false);
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 8 ms 508 KB Output is correct
4 Correct 18 ms 1656 KB Output is correct
5 Correct 60 ms 3704 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct

Subtask #3
45.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 381 ms 764 KB Output is correct
4 Correct 488 ms 1656 KB Output is correct
5 Correct 737 ms 1628 KB Output is correct
6 Correct 695 ms 2552 KB Output is correct
7 Correct 784 ms 2552 KB Output is correct
8 Correct 544 ms 3576 KB Output is correct
9 Correct 712 ms 3576 KB Output is correct
10 Execution timed out 827 ms 3576 KB Time limit exceeded