oj.uz

Submission #491782

# Submission time Handle Problem Language Result Execution time Memory
491782 2021-12-04T11:16:54 Z Alexandruabcde Climbers (RMI18_climbers) C++14
0 / 100
 264 ms 196276 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]);
    N = aux.size();
    for (int i = 1; i <= N; ++ i )
        V[i] = aux[i-1];
    V[N+1] = 0;
}

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-1]));

        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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Incorrect 1 ms 2124 KB Output isn't correct
3 Incorrect 6 ms 12108 KB Output isn't correct
4 Incorrect 39 ms 82764 KB Output isn't correct
5 Incorrect 116 ms 196276 KB Output isn't correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Incorrect 1 ms 972 KB Output isn't correct
4 Incorrect 1 ms 716 KB Output isn't correct
5 Incorrect 2 ms 3020 KB Output isn't correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Incorrect 1 ms 1996 KB Output isn't correct
3 Incorrect 80 ms 11392 KB Output isn't correct
4 Incorrect 179 ms 76032 KB Output isn't correct
5 Incorrect 191 ms 75444 KB Output isn't correct
6 Incorrect 192 ms 137716 KB Output isn't correct
7 Incorrect 264 ms 130160 KB Output isn't correct
8 Incorrect 193 ms 186080 KB Output isn't correct
9 Incorrect 237 ms 187848 KB Output isn't correct
10 Incorrect 256 ms 185612 KB Output isn't correct