Overview

When choosing to “harvest or not harvest” each tree, find the maximum total number of fruits that can be harvested under the constraint that if you harvest a tree, you cannot harvest the next \(K\) trees.

Analysis

This problem is a classic example of “maximum sum when you cannot select adjacent (or within a certain distance) elements simultaneously.”

• If you harvest tree \(i\), the next \(K\) trees (\(i+1\) through \(i+K\)) cannot be harvested.
• In other words, if you select tree \(i\), the most recent tree you could have previously selected is at most tree \(i-(K+1)\).

A naive approach of “exploring all choices while searching for the next harvestable tree” leads to an exponential number of options, which is too slow for \(N \le 2\times 10^5\) (TLE).
Instead, we use dynamic programming (DP) based on “the optimal value when considering the first \(i\) trees,” updating the optimal solution for each \(i\) in \(O(1)\).

As a concrete example, when \(K=2\), if you harvest tree \(i\), then trees \(i-1\) and \(i-2\) cannot be harvested, so the best combination is “optimal solution up to tree \(i-3\) + \(A_i\).”

Algorithm

We define the DP as follows:

• \(dp[i]\): “The maximum number of fruits that can be harvested when considering the first \(i\) trees (\(1 \sim i\))”

For the \(i\)-th tree, there are 2 choices:

1. Do not harvest
   Nothing changes, so it equals \(dp[i-1]\).
2. Harvest
   The most recent tree that could have been harvested is at most tree \(i-(K+1)\), so
   \(dp[i-(K+1)] + A_i\) (where we treat \(dp[0]=0\) when \(i-(K+1) \le 0\)).

Therefore, the transition is:

• \(t = \max(0,\, i-K-1)\)
• \(dp[i] = \max\bigl(dp[i-1],\ dp[t] + A_i\bigr)\)

Computing this sequentially from \(i=1\), the answer is \(dp[N]\).

(In the code, since the array is 0-indexed, \(A_i\) is referenced as A[i-1].)

Complexity

• Time complexity: \(O(N)\) (constant time update for each \(i\))
• Space complexity: \(O(N)\) (for the \(dp\) array)

Implementation Notes

• Since \(t = i-K-1\) can be negative, it is important to clamp it with max(0, t) and use \(dp[0]=0\).

• Using 0-indexed \(A\) and a 1-indexed style definition for \(dp\) representing “up to \(i\) trees” (with length \(N+1\)) makes the transition easier to write.

• Since \(N\) can be large, it is safer to use sys.stdin.readline for input.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * (N + 1)  # dp[i]: max fruits from first i trees

    for i in range(1, N + 1):
        take_prev = i - K - 1
        if take_prev < 0:
            take_prev = 0
        dp[i] = max(dp[i - 1], dp[take_prev] + A[i - 1])

    print(dp[N])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.