Submission #1161172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161172		just	밀림 점프 (APIO21_jumps)	C++20	4 / 100	656 ms	1114112 KiB

jumps

#include "bits/stdc++.h"
using namespace std;

#define all(x) (x).begin(), (x).end()
#define int long long
#define vec vector
#define pii pair<int, int>

#define X first
#define Y second

const int BIG = 1e18;

int n;
vec<int> heights;

vec<int> lst, nxt;

bool monotonic = true;

void init(signed N, vec<signed> H) {
    {
        n = N;
        assert(H.size() == n);
    
        heights.resize(n);
        for (int i = 0; i < n; i++) {
            heights[i] = H[i];
        }
    }
    

    for (int i = 0; i < n; i++) monotonic &= heights[i] == i + 1;


    lst.resize(n);
    nxt.resize(n);

    int mx = 0, idx = -1;
    for (int i = 0; i < n; i++) {
        lst[i] = idx;
        if (heights[i] > mx) {
            mx = heights[i];
            idx = i;
        }
    }

    mx = 0, idx = n;
    for (int i = n - 1; i >= 0; i--) {
        nxt[i] = idx;
        if (heights[i] > mx) {
            mx = heights[i];
            idx = i;
        }
        
    }
}

int a, b, c, d;

int dfs(int x) {
    if (c <= x && x <= d) return 0;

    if (lst[x] == -1 && nxt[x] == n) return BIG;
    if (lst[x] == -1) return dfs(nxt[x]) + 1;
    if (nxt[x] ==  n) return dfs(lst[x]) + 1;
    return min(dfs(lst[x]), dfs(nxt[x])) + 1;
}

int calc() {
    if (monotonic) { return c - b; };

    
    int ans = BIG;
    for (int i = a; i <= b; i++) {
        ans = min(ans, dfs(i));
    }

    return ans == BIG ? -1 : ans;
}

signed minimum_jumps(signed _A, signed _B, signed _C, signed _D) {
    a = _A, b = _B, c = _C, d = _D;
    return calc();
}


#ifdef debug
signed main() {}
#endif

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19