oj.uz

Submission #696359

# Submission time Handle Problem Language Result Execution time Memory
696359 2023-02-06T10:09:07 Z jhwest2 Climbers (RMI18_climbers) C++14
60 / 100
 800 ms 499728 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef array<int, 3> P;

const int N = 5050;
const ll INF = 1e18 + 10;

int n, a[N], p;
ll dp[2 * N][2 * N];
bool inq[2 * N][2 * N];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (p && a[p - 1] == x)
            continue;
        while (p >= 2 && (a[p - 2] < a[p - 1]) == (a[p - 1] < x))
            --p;
        a[p++] = x;
    }
    n = p;

    for (int i = 0; i <= 2 * n - 2; i++)
        for (int j = i; j <= 2 * n - 2; j++)
            dp[i][j] = INF;
    dp[0][2 * n - 2] = 0;

    auto go = [&](int x, int y, int tx, int ty) {
        int p = (x & 1) ? a[y / 2] : a[x / 2];
        int nx = (x & 1) ? (tx ? x + 1 : x - 1) : (tx ? x + 2 : x - 2);
        int ny = (y & 1) ? (ty ? y - 1 : y + 1) : (ty ? y - 2 : y + 2);
        if (nx < 0 || ny < 0 || nx > 2 * n - 2 || ny > 2 * n - 2)
            return P{ -1, -1, 0 };

        bool dx = (tx ? a[nx / 2 - 1] : a[nx / 2 + 1]) < a[nx / 2]; // true if climbing
        bool dy = (ty ? a[ny / 2 + 1] : a[ny / 2 - 1]) < a[ny / 2];

        if (dx != dy)
            return P{ -1, -1, 0 };

        if (a[nx / 2] == a[ny / 2])
            return P{ nx, ny, abs(a[nx / 2] - p) };
        if (dx == (a[nx / 2] < a[ny / 2]))
            return P{ nx, ty ? ny + 1 : ny - 1, abs(a[nx / 2] - p) };
        else
            return P{ tx ? nx - 1 : nx + 1, ny, abs(a[ny / 2] - p) };
    };
    vector<pair<int, int>> q;
    q.push_back({ 0, 2 * n - 2 });
    while (!q.empty()) {
        auto [l, r] = q.back(); q.pop_back();
        inq[l][r] = 0;

        for (int tx = 0; tx <= 1; tx++) for (int ty = 0; ty <= 1; ty++) {
            auto [x, y, d] = go(l, r, tx, ty);
            if (x != -1) {
                if (dp[x][y] > dp[l][r] + d) {
                    dp[x][y] = dp[l][r] + d;
                    if (!inq[x][y]) {
                        inq[x][y] = 1;
                        q.push_back({ x, y });
                    }
                }
            }
        }
    }
    ll ans = INF;
    for (int i = 0; i < n; i++)
        ans = min(ans, dp[2 * i][2 * i]);
    cout << ans;
}

Compilation message

climbers.cpp: In function 'int main()':
climbers.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         auto [l, r] = q.back(); q.pop_back();
      |              ^
climbers.cpp:59:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |             auto [x, y, d] = go(l, r, tx, ty);
      |                  ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 19 ms 33160 KB Output is correct
4 Correct 106 ms 199116 KB Output is correct
5 Correct 284 ms 499728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 724 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 23 ms 8708 KB Output is correct

Subtask #3
10.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 29 ms 5412 KB Output is correct
3 Execution timed out 1093 ms 24780 KB Time limit exceeded
4 Execution timed out 1101 ms 162344 KB Time limit exceeded
5 Execution timed out 1104 ms 177404 KB Time limit exceeded
6 Execution timed out 1104 ms 311144 KB Time limit exceeded
7 Execution timed out 1104 ms 285860 KB Time limit exceeded
8 Execution timed out 1115 ms 446292 KB Time limit exceeded
9 Execution timed out 1112 ms 435832 KB Time limit exceeded
10 Execution timed out 1109 ms 426780 KB Time limit exceeded