Overview

This problem involves harvesting fruits from \(N\) trees arranged in a row, where after harvesting from a tree, you cannot harvest from the next \(K\) trees. The goal is to maximize the total number of fruits harvested.

Analysis

At each tree, Takahashi has two possible actions: “harvest from this tree” or “do not harvest from this tree”.

• If harvesting: There must be a gap of at least \(K\) trees since the last harvested tree. In other words, if harvesting at the \(i\)-th tree, the most recent tree that could have been harvested is the \((i-K-1)\)-th tree or earlier.
• If not harvesting: The harvesting status up to the \((i-1)\)-th tree is carried over as is.

Since “the current state is determined based on previous states,” this problem has a structure that can be efficiently solved using dynamic programming (DP).

Since \(N\) can be as large as \(2 \times 10^5\), an \(O(N^2)\) solution using nested loops would be too slow. However, under the given constraints, an \(O(N)\) solution that only references the immediately relevant previous states is more than sufficient.

Algorithm

Define the DP table as follows:

• dp[i]: The maximum total number of fruits that can be harvested when considering trees up to the \(i\)-th tree.

For each \(i\) from \(1\) to \(N\), set dp[i] to the larger of the following two cases:

1. Not harvesting at the \(i\)-th tree

   • This equals the maximum value up to the \((i-1)\)-th tree.
   • Formula: dp[i-1]

2. Harvesting at the \(i\)-th tree

   • Add the fruits \(A_i\) from the \(i\)-th tree, plus the maximum value at the \((i-K-1)\)-th point, which is the latest point where harvesting was possible.
   • If \(i-K-1 \leq 0\), there were no previously harvested trees, so only \(A_i\) is added.
   • Formula: A[i-1] + dp[max(0, i-K-1)]

The final answer is dp[N].

Complexity

• Time complexity: \(O(N)\)
  • The DP table can be filled in a single loop over the \(N\) trees, making it very fast.
• Space complexity: \(O(N)\)
  • Memory is needed to maintain a DP table of length \(N+1\).

Implementation Notes

• Index adjustment: Arrays in programming languages are typically 0-indexed, but when thinking about DP transitions, managing them as 1-indexed (“result up to the \(i\)-th tree”) makes boundary conditions (such as when \(i=0\)) easier to handle.

• Handling large input: In Python, reading all input at once using sys.stdin.read().split() can be faster than calling input() repeatedly.

• Updating the maximum: Use max(val_skip, val_pick) to always maintain the optimal solution at each point.

  Source Code

import sys

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 番目までの木を考慮したときの収穫できる果物の合計個数の最大値
    # dp[0] = 0 (木が0本のときは0)
    dp = [0] * (N + 1)
    
    for i in range(1, N + 1):
        # i 番目の木 (インデックス A[i-1]) を収穫しない場合
        # 直前の状態 dp[i-1] を引き継ぐ
        val_skip = dp[i-1]
        
        # i 番目の木 (インデックス A[i-1]) を収穫する場合
        # 直後の K 本が収穫不可ということは、直前の K 本も収穫不可であったはず
        # つまり、最後に収穫できた可能性があるのは i-K-1 番目以前の木
        prev_idx = i - K - 1
        val_pick = A[i-1]
        if prev_idx > 0:
            val_pick += dp[prev_idx]
        
        # 収穫する場合としない場合の大きい方を採用する
        if val_skip > val_pick:
            dp[i] = val_skip
        else:
            dp[i] = val_pick
            
    # 全体の最大値を出力する
    print(dp[N])

if __name__ == '__main__':
    solve()

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