Submission #336745

#	Time	Username	Problem	Language	Result	Execution time	Memory
336745		Sorting	Climbers (RMI18_climbers)	C++17	5 / 100	111 ms	215916 KiB

climbers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll N = 5000 + 3;
const ll INF = 1e18;

void build_edges(ll pos1, ll pos2, bool exact, vector<array<ll, 4>> &adj);

ll n, a[N];
ll dist[N][N][2];

ll dijkstra(ll pos1, ll pos2, bool exact){
    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;

    for(ll pos1 = 0; pos1 < n; ++pos1)
        for(ll pos2 = pos1; pos2 < n; ++pos2)
            for(ll exact = 0; exact <= 1; ++exact)
                dist[pos1][pos2][exact] = INF;

    dist[pos1][pos2][exact] = 0;
    pq.push({0, pos1, pos2, exact});

    vector<array<ll, 4>> adj;
    while(!pq.empty()){
        auto [d, pos1, pos2, exact] = pq.top();
        pq.pop();

        if(d != dist[pos1][pos2][exact]) continue;
        if(pos1 == pos2) return d;

        adj.clear();
        build_edges(pos1, pos2, exact, adj);
        for(auto [pos1_to, pos2_to, exact_to, cost]: adj){
            ll cand = d + cost;
            if(cand < dist[pos1_to][pos2_to][exact_to]){
                dist[pos1_to][pos2_to][exact_to] = cand;
                pq.push({cand, pos1_to, pos2_to, exact_to});
            } 
        }
    }

    return INF;
}

void move_dp(ll mv1, ll mv2, ll pos1, ll pos2, bool exact, ll x, vector<array<ll, 4>> &adj){
    //cout << mv1 << " " << mv2 << " " << pos1 << " " << pos2 << " " << exact <<  " " << x << endl;
    if(a[mv1] > x && x > a[mv2]) return;
    if(a[mv1] < x && x < a[mv2]) return;

    ll new_x;
    if(a[mv1] < x) new_x = max(a[mv1], a[mv2]);
    else new_x = min(a[mv1], a[mv2]);

    ll new_exact = (a[mv1] == new_x) ? 0 : 1;
    
    ll new_pos1 = (a[mv1] == new_x) ? mv1 : pos1;
    ll new_pos2 = (a[mv2] == new_x) ? mv2 : pos2;
    if(a[pos1] == x && a[mv1] != new_x){
        if(mv1 == pos1 + 1) new_pos1 = pos1;
        else new_pos1 = pos1 - 1;
    }
    if(a[pos2] == x && a[mv2] != new_x){
        if(mv2 == pos2 - 1) new_pos2 = pos2;
        else new_pos2 = pos2 + 1;
    }

    adj.push_back({new_pos1, new_pos2, new_exact, abs(x - new_x)});
    
    //cout << pos1 << " " << pos2 << " " << exact << " -> " << new_pos1 << " " << new_pos2 << " " << new_exact << " " << abs(x - new_x) << endl;
}

void build_edges(ll pos1, ll pos2, bool exact, vector<array<ll, 4>> &adj){
    ll x = !exact ? a[pos1] : a[pos2];
    bool e1 = (x == a[pos1]), e2 = (x == a[pos2]);
    vector<ll> v1, v2;

    if(e1){
        v1.push_back(pos1 + 1);
        if(pos1) v1.push_back(pos1 - 1);
    }
    else{
        v1.push_back(pos1 + 1);
        v1.push_back(pos1);
    }

    if(e2){
        v2.push_back(pos2 - 1);
        if(pos2 != n - 1) v2.push_back(pos2 + 1);
    }
    else{
        v2.push_back(pos2 - 1);
        v2.push_back(pos2);
    }

    move_dp(v1[0], v2[0], pos1, pos2, exact, x, adj);
    if(v2.size() == 2) move_dp(v1[0], v2[1], pos1, pos2, exact, x, adj);
    if(v1.size() == 2) move_dp(v1[1], v2[0], pos1, pos2, exact, x, adj);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(ll i = 0; i < n; ++i)
        cin >> a[i];

    vector<ll> v;
    v.push_back(a[0]);

    for(ll i = 1; i < n - 1; ++i){
        if(v.back() <= a[i] && a[i] <= a[i + 1])
            continue;
        if(v.back() >= a[i] && a[i] >= a[i + 1])
            continue;
        v.push_back(a[i]);
    }
    v.push_back(a[n - 1]);

    n = v.size();
    for(ll i = 0; i < n; ++i)
        a[i] = v[i];

    //build_edges(0, n - 1, 0);
    ll ans = dijkstra(0, n - 1, 0);

    if(ans == INF) cout << "NO\n";
    else cout << ans << "\n";
}

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