Submission #491784

#	Time	Username	Problem	Language	Result	Execution time	Memory
491784		Alexandruabcde	Climbers (RMI18_climbers)	C++14	100 / 100	216 ms	196228 KiB

climbers

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr int NMAX = 5005;
constexpr LL INF = 1LL * 1e18;
typedef pair <LL, pair <int, int> > PLLII;

int N;
LL dp[NMAX][NMAX];
int V[NMAX];

LL modul (LL x) {
    if (x < 0) x = -x;

    return x;
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> V[i];
    vector <int> aux;
    aux.push_back(V[1]);
    for (int i = 2; i < N; ++ i ) {
        if (V[i-1] <= V[i] && V[i] <= V[i+1]) continue;

        if (V[i-1] >= V[i] && V[i] >= V[i+1]) continue;

        aux.push_back(V[i]);
    }
    aux.push_back(V[N]);
    for (int i = aux.size()+1; i <= N; ++ i )
        V[i] = 0;
    N = aux.size();
    for (int i = 1; i <= N; ++ i )
        V[i] = aux[i-1];
}

priority_queue< PLLII, vector<PLLII>, greater<PLLII> > H;

bool Good (int varf, int drum) {
    if (V[drum] < V[drum+1])
        return (V[drum] <= V[varf] && V[varf] <= V[drum+1]);
    else
        return (V[drum] >= V[varf] && V[varf] >= V[drum+1]);
}

void PushBack (int A, int B, LL val) {
    if (val < dp[A][B]) {
        dp[A][B] = val;
        H.push({val, {A, B}});
    }
}

void Solve () {
    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= N; ++ j )
            dp[i][j] = INF;
    dp[1][N-1] = 0;
    H.push({0, {1, N-1}});

    while (!H.empty()) {
        PLLII x = H.top();
        H.pop();

        if (x.second.first == x.second.second || x.second.first == x.second.second + 1) {
            cout << x.first << '\n';
            return;
        }

        if (x.first != dp[x.second.first][x.second.second]) continue;

        int vf = x.second.first;
        int dr = x.second.second;
        LL cost = x.first;

        if (vf < N && Good(vf + 1, dr))
            PushBack(vf+1, dr, cost + modul(V[vf+1] - V[vf]));

        if (vf > 1 && Good(vf - 1, dr))
            PushBack(vf-1, dr, cost + modul(V[vf] - V[vf-1]));

        if (Good(dr, vf))
            PushBack(dr, vf, cost + modul(V[vf] - V[dr]));

        if (vf > 1 && Good(dr, vf-1))
            PushBack(dr, vf-1, cost + modul(V[vf] - V[dr]));

        if (Good(dr+1, vf))
            PushBack(dr+1, vf, cost + modul(V[vf] - V[dr+1]));

        if (vf > 1 && Good(dr+1, vf-1))
            PushBack(dr+1, vf-1, cost + modul(V[vf] - V[dr+1]));
    }

    cout << -1 << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

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