Overview

Given a row of fruit trees, find the maximum number of fruits that can be harvested under the constraint that after harvesting from a tree, you cannot harvest from the next \(K\) trees.

Analysis

At first glance, this problem might seem solvable by exhaustively searching “which trees to harvest from,” but since the number of trees \(N\) can be up to \(2 \times 10^5\), an exponential-time search is infeasible.

The key observation is that the choice to “harvest from the \(i\)-th tree” depends on the position of the last tree previously harvested. Specifically, to harvest from the \(i\)-th tree, the previous harvest must have been at tree \(i - K - 1\) or earlier.

For problems like this where we need to “find the maximum value under certain constraints,” dynamic programming (DP) is effective.

DP Definition

• \(dp[i]\) := the maximum number of fruits harvested up to and including the \(i\)-th tree, where the \(i\)-th tree is the last tree harvested

The transition is as follows: $\( dp[i] = \max_{j \leq i - K - 1} dp[j] + A[i] \)$

However, as written, this requires up to \(O(N)\) computation for each \(i\), resulting in \(O(N^2)\) overall, which is too slow.

Optimizing the Complexity

All we need is “the maximum value of past \(dp[j]\),” so we can speed this up by maintaining a prefix maximum.

• \(prefix\_max[i] = \max(dp[0], dp[1], \dots, dp[i])\)

This way, instead of looping each time to compute \(dp[i]\), we simply reference \(prefix\_max[i - K - 1]\). This reduces the complexity to \(O(N)\).

Algorithm

1. Read input (using sys.stdin.read for faster I/O).
2. Update \(dp[i]\) as “the maximum value when the \(i\)-th tree is the last tree harvested.”
3. Maintain \(prefix\_max[i]\) as “the maximum of \(dp[0]\) through \(dp[i]\).”
4. For each \(i\), compute \(dp[i] = (i - K - 1 \geq 0\ ?\ prefix\_max[i - K - 1]\ :\ 0) + A[i]\).
5. The final answer is \(prefix\_max[N - 1]\) (since we don’t know which tree will be the last one harvested, we take the overall maximum).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since the input can be very large, use sys.stdin.read for fast input processing.
• Use a prefix maximum table to make each transition computation constant time.
• Be careful with index boundary conditions (\(i - K - 1 \geq 0\)).

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # dp[i] := i番目の木まで見て、i番目の木で収穫する場合の最大値
    # ただし、i-K-1以前で最後に収穫した木をjとすると、j <= i-K-1
    # つまり、dp[i] = max_{j <= i-K-1} dp[j] + A[i]
    
    # 最適化: prefix_max[i] = max(dp[0], dp[1], ..., dp[i])
    # dp[i] = (i-K-1 >= 0 ? prefix_max[i-K-1] : 0) + A[i]

    dp = [0] * N
    prefix_max = [0] * N

    for i in range(N):
        prev_max = 0
        if i - K - 1 >= 0:
            prev_max = prefix_max[i - K - 1]
        dp[i] = prev_max + A[i]
        prefix_max[i] = max(prefix_max[i-1] if i > 0 else 0, dp[i])
    
    print(max(prefix_max))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.