Overview

Given \(N\) apple trees lined up in a row, we need to find the total number of apples Takahashi harvests when he follows a certain rule.

Analysis

Takahashi harvests all apples from \(K\) consecutive trees, then skips the next one tree as a break, and repeats this process. In other words, he proceeds as: harvest \(K\) trees → skip 1 tree → harvest \(K\) trees → skip 1 tree → …

For example, when \(N = 8, K = 2\): - Harvest trees 1, 2 (total of 2 trees) - Skip tree 3 - Harvest trees 4, 5 - Skip tree 6 - Harvest trees 7, 8

In this way, the pattern “take \(K\), skip 1” repeats.

As a straightforward approach, we can simulate the process of “adding \(K\) trees, then skipping the next one” at each step, and since the constraint is \(N \leq 10^6\), this is fast enough. However, if \(K\) were extremely large or there were more complex conditions, a brute-force approach could potentially be too slow.

In this problem, though, a simple simulation can solve it efficiently.

Algorithm

1. Use a variable i to track the current position (starting at 0).
2. While i is less than \(N\), repeat the following:
   • Add all apples from trees at positions i to min(i + K, N) to the total.
   • Then, advance i by K + 1 to handle both the \(K\) harvested trees and the 1 skipped tree at once.
3. Output the total.

In this way, we sequentially identify the trees that Takahashi actually harvests and sum up their apple counts.

Complexity

• Time complexity: \(O(N)\) Each tree is visited at most once, so the processing runs in linear time.
• Space complexity: \(O(N)\) \(O(N)\) is needed to store the input array \(D\).

Implementation Notes

• It is important to use min as in for j in range(i, min(i + K, N)) to prevent out-of-bounds access.

• Be careful with the loop termination condition so that there are no issues even if there aren’t enough trees in the last segment.

• A key point is that i += K + 1 advances both the harvesting and skipping in one step.

  Source Code

N, K = map(int, input().split())
D = list(map(int, input().split()))

total = 0
i = 0

while i < N:
    # 収穫する木: i から i+K-1 まで
    for j in range(i, min(i + K, N)):
        total += D[j]
    # 次のK+1個分をスキップ (K個収穫 + 1個休憩)
    i += K + 1

print(total)

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