Overview

This is a problem of finding the optimal path to cross a river by hopping on stepping stones while minimizing the cost written on the stones.

Analysis

This problem can be solved using a typical “Dynamic Programming (DP)” approach.
Let \(dp[i]\) be the minimum cost to reach stone \(i\).
Stone \(i\) can be reached by jumping from any stone between stone \(i-K\) and stone \(i-1\), so we can update as follows:

\[ dp[i] = \min_{j=\max(0, i-K)}^{i-1} (dp[j]) + A[i] \]

However, with this naive DP, we need to examine up to \(K\) candidates for each \(i\), resulting in a worst-case time complexity of \(O(NK)\).
Given the constraints, \(N\) and \(K\) can be up to \(10^6\), making the total \(10^{12}\), which cannot be solved within a practical time limit (TLE).

Therefore, we solve this problem efficiently using a data structure that can quickly retrieve and update the minimum value over an interval: the “Sliding Window Minimum (implemented with a deque).”
Specifically, by maintaining the minimum value of \(dp[j]\) within a certain range in the deque at all times, we can retrieve the minimum value in \(O(1)\) at each step.

Algorithm

1. Prepare a DP array dp and set the initial value dp[0] = A[0] (0-indexed).
2. Prepare a deque to manage the minimum values, initially containing index 0.
3. For each stone \(i = 1\) to \(N-1\):
   • Remove the front of the deque if it is outside the range \([i-K, i-1]\).
   • Update with dp[i] = dp[front of deque] + A[i].
   • Remove useless elements from the back of the deque that have \(dp\) values greater than or equal to dp[i], then add i.
4. Finally, dp[N-1] is the answer.

By using a deque in this way, we efficiently handle the retrieval and update of the interval minimum.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Each element is added to and removed from the deque at most once, so the entire process runs in linear time.

Implementation Notes

• Stone numbers are 1-indexed, but handling them as 0-indexed internally simplifies the implementation.

• The deque stores indices, and comparisons are made using the corresponding dp values.

• After computing dp[i], it is necessary to remove useless elements from the back of the deque before adding the new element.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # dp[i] := 石 i に到達するための最小コスト
    # 石の番号は 0-indexed で扱う（元の問題は 1-indexed）
    dp = [float('inf')] * N
    dp[0] = A[0]
    
    # 最小コストを保持する deque (sliding window minimum)
    dq = deque()
    dq.append(0)
    
    for i in range(1, N):
        # 範囲外のインデックスを削除
        while dq and dq[0] < i - K:
            dq.popleft()
        
        # 現在の最小コストを使って dp[i] を更新
        dp[i] = dp[dq[0]] + A[i]
        
        # dp[i] を deque に追加するために、無駄な要素を削除
        while dq and dp[dq[-1]] >= dp[i]:
            dq.pop()
        dq.append(i)
    
    print(dp[N - 1])

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.