Wario Kart II

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

#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)(x).size()                                 // signed size: avoids the unsigned .size() wrap bug

using ll  = long long;
using pii = pair<int,int>;
using vi  = vector<int>;

#ifdef LOCAL                                                    // compile with -DLOCAL to enable, silent on the judge
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", dbg_out(__VA_ARGS__)
template<class T> void dbg_out(T x) { cerr << x << '\n'; }
template<class T, class... R> void dbg_out(T x, R... r) { cerr << x << ", "; dbg_out(r...); }
#else
#define dbg(...)
#endif

int main() {
    cin.tie(0)->sync_with_stdio(0);  

    int n,k; cin >> n >>  k;  // n length. k cooldown
    vi a(n); for (auto &x : a) cin >> x;
    double min_time[n+1];
    
    for (int i = 0; i < n+1; i++){min_time[i] = n;}
    min_time[0] = 0;



    for (int i = 0; i < n; i++){
        min_time[i+1] = min(min_time[i+1], min_time[i] + 1);

        int next_jump = i + a[i];
        if (next_jump > n ){
            min_time[n] = min( min_time[n],  min_time[i] +  ((double)(n-i) /  (double)a[i]));
        }else {
            // for n
            if (next_jump + k > n){
                min_time[n] = min(min_time[n], min_time[i] + 1 + (n-next_jump));
            } else{
                
                min_time[next_jump + k] = min(min_time[next_jump + k], min_time[i] + 1 + k);
            }
        }

    }
    cout << fixed << setprecision(20);
    cout << min_time[n];

    // cout << ;
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED