Overview

This problem asks you to find the maximum total coins you can collect while jumping rightward up to \(K\) stones at a time to reach stone \(N\), where each stone has some coins (possibly negative).

Analysis

Since you can only move rightward and never stand on the same stone twice, a dynamic programming (DP) approach that considers “the maximum coins collected upon reaching stone \(i\)” is natural.

The stone you were on immediately before arriving at stone \(i\) must be one of stones \(i-K, i-K+1, \ldots, i-1\) (within valid range). Therefore: - The maximum value upon reaching stone \(i\) is “the maximum DP value among reachable previous stones + \(A_i\)”.

A naive implementation would check up to \(K\) candidates for each \(i\) to find the maximum, resulting in: - \(O(NK)\) time complexity, which for \(N \le 2 \times 10^5\) could be around \(4 \times 10^{10}\) operations in the worst case, causing TLE.

What we need is to efficiently update and retrieve for each \(i\): - The maximum of \(dp\) over the interval \([i-K,\, i-1]\)

This is the “sliding window maximum” problem, which can be handled in \(O(1)\) amortized time using a monotonic queue (deque).

Algorithm

1. DP Definition

Let \(dp[i]\) be “the maximum total coins collected after reaching stone \((i+1)\) (stone \(i\) in 0-indexed) and collecting its coins.”

• Initial value: We start standing on stone 1, so \(dp[0] = A_1\)
• Transition (for \(i \ge 1\)):
  • The stone immediately before reaching stone \(i\) is one of \(i-K\) through \(i-1\)
  • Therefore
    \(dp[i] = A_{i+1} + \max\{ dp[j] \mid i-K \le j \le i-1 \}\)
    (where \(j \ge 0\))

2. Managing Interval Maximum with a Monotonic Queue

We maintain indices in a deque such that the corresponding \(dp\) values are in decreasing order (monotonically non-increasing).

For each \(i=1..N-1\), we perform the following:

1. Remove out-of-range elements
   If the front of the deque is less than \(i-K\) (i.e., it no longer falls within \([i-K, i-1]\)), remove it from the front.
2. Transition using the maximum value
   The front of the deque always holds the index with the maximum \(dp\) value in the interval, so
   \(dp[i] = A[i] + dp[deque[0]]\)
3. Maintain monotonicity
   If the new \(dp[i]\) is greater than or equal to the \(dp\) value at the back of the deque, those back elements can never be the maximum in the future, so remove them from the back. Then append \(i\).

Since each index enters and leaves the deque at most once, the entire process runs in \(O(N)\).

(Simple intuitive example)
“Where to jump next” is optimally determined by always coming from “the most profitable state (largest dp) among the previous \(K\) stones,” so we keep that “best candidate” at the front of the deque at all times.

Complexity

• Time complexity: \(O(N)\) (each element enters and leaves the deque at most once)
• Space complexity: \(O(N)\) (for the \(dp\) array and the deque)

Implementation Notes

• Using 0-indexed throughout makes the implementation cleaner (the code follows this convention).

• The condition for removing out-of-range elements from the deque is q[0] < i - K (reachable previous stones must have index \(i-K\) or greater).

• For maintaining monotonicity, we pop from the back while dp[q[-1]] <= dp[i]. Using <= allows us to discard the older element when values are equal, preventing the deque from growing unnecessarily long.

• Since \(A_i\) can be negative, greedy strategies like “step on as many stones as possible” do not work, making DP necessary.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    dp = [0] * N
    dp[0] = A[0]
    
    q = deque([0])  # indices with dp in decreasing order
    
    for i in range(1, N):
        while q and q[0] < i - K:
            q.popleft()
        dp[i] = A[i] + dp[q[0]]
        while q and dp[q[-1]] <= dp[i]:
            q.pop()
        q.append(i)
    
    print(dp[-1])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.