Overview

In the stone jumping game, you move by jumping across stones arranged in a line while collecting coins. The problem asks for the maximum number of coins that can be obtained by the time you reach stone N.

Analysis

Let dp[i] be the maximum number of coins when reaching stone i. Then dp[i] can be computed as “the maximum dp value among the previous K stones + A[i]”. However, if we naively check the previous K stones for each stone, the time complexity becomes O(NK). Since both N and K can be up to 200,000, the worst case would require 40 billion computations, which would not fit within the time limit. Therefore, we need a data structure that can efficiently compute the sliding window maximum.

Algorithm

We use dynamic programming combined with a sliding window maximum technique using a double-ended queue (deque). 1. Initialize with dp[0] = A0 2. Prepare a deque (dq) and add index 0 3. Process sequentially from i=1 to N-1: - Remove indices from the front of the deque that are outside the window (before i-K) - Compute dp[i] = dp[front of dq] + A[i] - Remove elements from the back of the deque whose dp values are less than or equal to the current dpi - Add the current index i to the back of the deque

The deque is always maintained so that dp values are monotonically decreasing (the back has the smallest value), and the index with the maximum value within the window is always at the front. This allows us to retrieve the maximum value in O(1) at each step.

Complexity

• Time complexity: \(O(N)\) (each index is added to and removed from the deque at most once)
• Space complexity: \(O(N)\) (used for the dp array and the deque)

Implementation Notes

• Store indices in the deque and remove unnecessary indices based on dp value comparisons

• Ensure that indices outside the window range are properly removed during deque operations

• Initialize so that the first stone (index 0) is always added to the deque

• The implementation must handle negative coin values as well

  Source Code

import collections

def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    dp = [0] * N
    dp[0] = A[0]
    dq = collections.deque()
    dq.append(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[-1])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.