Overview

Each stone has a cost \(A_i\), and you can jump up to \(K\) stones ahead. The problem asks for the minimum total cost to reach stone \(N\) from stone \(1\).

Analysis

Just before reaching stone \(i\), you must have jumped from some stone \(j\) (\(i-K \le j \le i-1\)). Therefore, the “minimum cost to reach stone \(i\)” can be updated using the minimum value among the preceding candidates.

• Define \(dp[i]\) as “the minimum total cost when landing on stone \(i\)”. Then: $\( dp[i] = A_i + \min\{dp[j] \mid i-K \le j \le i-1\} \)$ (ignoring out-of-range indices).

If we naively compute this formula, for each \(i\) we examine up to \(K\) candidates to find the minimum, resulting in \(O(NK)\).
Since the constraint is \(N \le 10^6\), if \(K \approx N\) for example, this becomes on the order of \(10^{12}\) operations, which will certainly TLE.

What we need is a way to efficiently update the “minimum over a sliding window of length \(K\)”: $\( \min\{dp[i-K], dp[i-K+1], \ldots, dp[i-1]\} \)$

Algorithm

We use a Monotone Queue to retrieve the “minimum of the last \(K\) \(dp\) values” in \(O(1)\) (amortized).

Procedure

1. Set \(dp[1]=A_1\), then for each subsequent \(i\), compute \(dp[i]=A_i+\text{(minimum of the last } K \text{ } dp \text{ values)}\).
2. Maintain a deque (double-ended queue) that stores “indices that are candidates for the minimum”.
   • Inside the deque, maintain the invariant that \(dp\) values are monotonically increasing
     (the front always holds the index with the smallest \(dp\) value).
3. For each \(i\):
   • Remove indices from the front that are out of range (\(< i-K\))
   • The front index gives the “minimum \(dp\) within the window”, so use it to compute: $\( dp[i] = A_i + dp[\text{deque[0]}] \)$
   • When adding the new \(dp[i]\), remove from the back any indices whose \(dp\) values are \(\ge dp[i]\) (they are no longer needed), then append \(i\) to the back

Why is it safe to remove from the back?

When a back index \(t\) has \(dp[t] \ge dp[i]\), in any future window where both \(t\) and \(i\) are candidates, \(i\) will always be at least as cheap as \(t\), so \(t\) can never be the minimum candidate. Therefore, discarding it does not affect the correctness of the answer.

Complexity

• Time complexity: \(O(N)\)
  (Each index enters the deque at most once and leaves at most once, so the total is amortized \(O(N)\))
• Space complexity: \(O(N)\)
  (The \(dp\) array is of size \(N\), and the deque holds at most \(N\) elements)

Implementation Notes

• Since \(N=10^6\), I/O can become a bottleneck in Python. The code uses sys.stdin.buffer.read() with a custom parser for speedup.

• The deque dq stores “indices”, and comparisons are done using dp[index].

• Out-of-range removal is done as while dq[0] < i-K: dq.popleft(), ensuring the front of the deque always holds the “usable minimum candidate”.

• Costs can be on the order of \(10^9 \times 10^6\), but since Python’s int has arbitrary precision, there is no concern about overflow.

  Source Code

import sys
from collections import deque

def main():
    data = memoryview(sys.stdin.buffer.read())
    ndata = len(data)
    idx = 0

    def read_int():
        nonlocal idx
        while idx < ndata and data[idx] <= 32:
            idx += 1
        num = 0
        while idx < ndata and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return num

    N = read_int()
    K = read_int()
    dp = [0] * N
    for i in range(N):
        dp[i] = read_int()

    dq = deque([0])  # indices with increasing dp
    for i in range(1, N):
        limit = i - K
        while dq[0] < limit:
            dq.popleft()
        dp[i] = dp[i] + dp[dq[0]]
        while dq and dp[dq[-1]] >= dp[i]:
            dq.pop()
        dq.append(i)

    sys.stdout.write(str(dp[-1]))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.