Overview

This problem asks us to find the minimum total cost of stones stepped on when Takahashi jumps from stone \(1\) to stone \(N\), where he can jump to at most \(K\) stones ahead at each step.

Approach

We first consider using dynamic programming (DP). To align with the implementation, we treat stone numbers as \(0\)-indexed (from \(0\) to \(N-1\)). Define dp[i] as “the minimum cost to reach stone \(i\).” Stone \(i\) can be reached by jumping from any of the stones \(i-K, i-K+1, \ldots, i-1\). Therefore, the transition formula is as follows:

\[ dp[i] = \min_{1 \leq j \leq \min(i, K)} (dp[i-j]) + A_i \]

However, if we naively compute this formula with a loop, we perform up to \(K\) comparisons for each \(i\), resulting in an overall time complexity of \(O(NK)\). Since the constraints allow \(N\) and \(K\) to be up to \(10^6\), the worst case would reach on the order of \(10^{12}\) operations, resulting in TLE (Time Limit Exceeded).

To solve this, we need a way to efficiently find the minimum value within a sliding window of length \(K\).

Algorithm

To efficiently find the minimum value over a range, we use the “Sliding Window Minimum” technique. This employs a double-ended queue (deque).

The queue stores “indices of stones that are candidates for the minimum value,” and is maintained so that the following properties always hold: - The indices in the queue are in ascending order (oldest first) - The dp values corresponding to the indices in the queue are monotonically increasing (the front always holds the minimum value)

When computing stone \(i\), we operate the queue with the following specific steps:

1. Remove outdated elements If the index at the front of the queue is less than \(i-K\) (meaning it is now too far to jump from), remove it from the front of the queue (popleft).
2. Retrieve the minimum and update At this point, the front of the queue is guaranteed to hold the index with the minimum dp value in the range \([i-K, i-1]\). Using this, we compute dp[i] = dp[dq[0]] + A[i].
3. Remove unnecessary elements Before adding the newly computed dp[i] to the queue, remove all indices from the back of the queue that have dp values greater than or equal to dp[i] (pop). This is because these elements have values larger than dp[i] and are also older than dp[i], so they can never become the minimum of any future window.
4. Add the new element Append the current index \(i\) to the back of the queue.

Complexity

• Time complexity: \(O(N)\) Each index \(i\) is added to the queue at most once and removed at most once. Therefore, the total number of times the inner while loop executes is at most \(N\), dramatically improving the time complexity from \(O(NK)\) to \(O(N)\).
• Space complexity: \(O(N)\) We use a DP array of \(N\) elements and a queue that can hold up to \(N\) elements, resulting in \(O(N)\).

Implementation Notes

• Using a double-ended queue: In Python, collections.deque allows \(O(1)\) addition and removal of elements from both ends. Be careful that using a list (array) as a substitute would cost \(O(N)\) for removal from the front.

• Fast I/O: Since the input can contain up to \(10^6\) numbers, instead of calling input() in a loop, we use sys.stdin.read().split() to read all input at once, significantly reducing execution time.

  Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(x) for x in input_data[2:N+2]]
    
    dp = [0] * N
    dp[0] = A[0]
    
    dq = deque([0])
    
    for i in range(1, N):
        while dq and dq[0] < i - K:
            dq.popleft()
            
        dp[i] = dp[dq[0]] + A[i]
        
        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 gemini-3.1-pro-thinking.