oj.uz

Submission #491784

# Submission time Handle Problem Language Result Execution time Memory
491784 2021-12-04T11:32:14 Z Alexandruabcde Climbers (RMI18_climbers) C++14
100 / 100
 216 ms 196228 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 2124 KB Output is correct
3 Correct 7 ms 12108 KB Output is correct
4 Correct 38 ms 82736 KB Output is correct
5 Correct 97 ms 196228 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 3020 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 716 KB Output is correct
2 Correct 1 ms 1996 KB Output is correct
3 Correct 64 ms 11388 KB Output is correct
4 Correct 125 ms 75952 KB Output is correct
5 Correct 162 ms 75492 KB Output is correct
6 Correct 176 ms 137704 KB Output is correct
7 Correct 185 ms 130212 KB Output is correct
8 Correct 173 ms 186060 KB Output is correct
9 Correct 216 ms 187844 KB Output is correct
10 Correct 208 ms 185532 KB Output is correct