Overview

This is a problem where you have \(N\) stones lined up across a river, and you can jump forward by at most \(K\) stones at a time, collecting coins on the stones to maximize the total. This problem can be solved using dynamic programming (DP), but a naive implementation is too slow, so we speed it up using a technique called sliding window maximum.

Analysis

Basic Dynamic Programming (DP)

First, consider the following DP: - \(dp[i]\): the maximum total number of coins obtainable when reaching stone \(i\)

The state immediately before reaching stone \(i\) is one of stones \(i-K, i-K+1, \ldots, i-1\). Therefore, the transition is as follows: - \(dp[i] = A_i + \max_{i-K \leq j < i} (dp[j])\) - Initial condition: \(dp[1] = A_1\)

Computational Complexity Issue

When computing each \(dp[i]\) according to this transition, we need to find the maximum among the previous \(K\) elements for each \(i\). - Number of stones \(N\): up to \(2 \times 10^5\) - Jump distance \(K\): up to \(N-1\)

If we naively find the maximum using a loop, the overall time complexity becomes \(O(N \times K)\), which in the worst case requires \(O(N^2) \approx 4 \times 10^{10}\) operations. This far exceeds typical time limits (2 seconds).

Idea for Optimization

To solve the problem of “efficiently obtaining the maximum value within a specific range (window),” we use an algorithm called sliding window maximum. This technique uses a deque (double-ended queue) to obtain the maximum within the window in \(O(1)\), and \(O(N)\) overall.

Algorithm

Sliding Window Maximum (Using a Deque)

The deque maintains “indices of elements that could potentially become the maximum in the future.” Specifically, the \(dp\) values corresponding to the indices in the deque are always maintained in descending order (from largest to smallest).

1. Removing old elements: If the index at the front of the deque is more than \(K\) away from the current stone (\(j < i-K\)), remove that index from the deque.
2. Obtaining the maximum: The index at the front of the deque points to the element with the largest \(dp\) value in the range \([i-K, i-1]\). Use this to compute \(dp[i] = A_i + dp[\text{front}]\).
3. Adding a new element: When adding \(dp[i]\) to the deque, remove all indices from the back of the deque whose values are less than or equal to \(dp[i]\). Then, add \(i\) to the back.
   • This is because once a newer element (further to the right) with a value greater than or equal to \(dp[i]\) appears, older elements with smaller values will never be selected as the maximum in the future.

With these operations, each element enters the deque exactly once and leaves exactly once, so the overall time complexity is kept at \(O(N)\).

Complexity

• Time complexity: \(O(N)\)
  • The addition and removal operations on the deque are performed at most once per stone, so the total time is proportional to \(N\).
• Space complexity: \(O(N)\)
  • The \(dp\) array and the deque have a maximum size of \(N\).

Implementation Notes

• Using a deque: In Python, collections.deque allows efficient addition and removal from both the front and back.

• Index management: Stone numbers start from 1, but handling them as 0-indexed (from \(0\) to \(N-1\)) in the program makes implementation smoother.

• Initial value: Since the first stone (stone 1) is always visited, we start with dp[0] = A[0].

  Source Code

import sys
from collections import deque

def solve():
    # 標準入力からすべてのデータを読み込み、スペースや改行で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 石の数, K: 一度に跳べる最大距離
    N = int(input_data[0])
    K = int(input_data[1])
    # A: 各石の上にあるコインの枚数 (0-indexedで管理)
    A = list(map(int, input_data[2:]))
    
    # dp[i] は石 i+1 に到達したときに獲得できるコインの合計の最大値を保持します
    # 石 1 は A[0], 石 N は A[N-1] に対応します
    dp = [0] * N
    dp[0] = A[0]
    
    # スライディングウィンドウ内の最大値を効率的に取得するために
    # デック（両端キュー）を用いたスライディングウィンドウ最大値のアルゴリズムを使用します。
    # dq には dp のインデックスを格納し、dp[dq[j]] が降順になるように維持します。
    dq = deque([0])
    
    for i in range(1, N):
        # 現在の石 i に到達可能な範囲は [i-K, i-1] です。
        # デックの先頭にあるインデックスがこの範囲外（i-K 未満）になった場合、取り除きます。
        if dq and dq[0] < i - K:
            dq.popleft()
        
        # デックの先頭にあるインデックスが、範囲内 [i-K, i-1] で dp の値が最大となるインデックスです。
        dp[i] = A[i] + dp[dq[0]]
        
        # 新しく計算した dp[i] をデックに追加します。
        # 降順を維持するため、dp[i] 以下の値を持つ既存のインデックスを末尾から取り除きます。
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        
        dq.append(i)
        
    # 石 N (インデックス N-1) に到達したときの最大値を出力します
    print(dp[N-1])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.