Overview

There are \(N\) trees lined up, and the number of fruits that can be harvested from each tree is given. The problem asks to find the minimum total number of fruits that can be harvested when selecting “consecutive \(K\) trees” from among them.

Analysis

Naive Approach

The simplest method is to calculate the sum of \(K\) trees for every possible starting position. - Calculate the sum from the 1st to the \(K\)-th tree - Calculate the sum from the 2nd to the \((K+1)\)-th tree - … - Calculate the sum from the \((N-K+1)\)-th to the \(N\)-th tree

However, this method takes \(O(K)\) time to compute each sum, and repeating this approximately \(N\) times results in an overall time complexity of \(O(N \times K)\). Given the constraints of this problem where \(N, K \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which cannot finish within the time limit (typically around 2 seconds).

Efficient Approach (Sliding Window)

Notice that when comparing the sums of adjacent ranges, most elements overlap. For example, with \(K=3\), when moving from “trees 1–3” to “trees 2–4”: - Sum of trees 1–3: \(A_1 + A_2 + A_3\) - Sum of trees 2–4: \(A_2 + A_3 + A_4\)

The difference between these two is only “the newly entering \(A_4\)” and “the departing \(A_1\)”. In other words, if we know the sum of the previous range, we can compute the sum of the next range with just two operations — “add the new value and subtract the old value” — in \(O(1)\) time.

Algorithm

Sliding Window Method

1. First, calculate the sum of the first \(K\) trees from the left as current_sum. Set this as the tentative minimum min_sum.
2. Slide the window one position to the right at a time. Specifically, repeat the following for \(i = 0\) to \(N-K-1\):
   • Subtract \(A_i\) from current_sum and add \(A_{i+K}\).
   • Compare the updated current_sum with min_sum, and set the smaller one as the new min_sum.
3. The final min_sum is the answer.

Complexity

• Time Complexity: \(O(N)\)
  • Computing the initial sum of \(K\) elements takes \(O(K)\), and the subsequent sliding operations take \(O(N-K)\), so the overall complexity is \(O(N)\). This runs sufficiently fast even when \(N=2 \times 10^5\).
• Space Complexity: \(O(N)\)
  • Memory is needed to store the \(N\) input elements in a list.

Implementation Notes

• Initializing the sum: When computing the sum of the first \(K\) elements, in Python you can write it concisely using sum(a[:k]).

• Loop range: Care must be taken with the loop termination condition to avoid going out of bounds (IndexError). When removing the \(i\)-th element and adding the \((i+k)\)-th element, the loop should run so that \(i+k\) reaches up to \(n-1\).

• Handling large values: The total number of fruits can reach up to \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\), but since Python natively supports arbitrary-precision integers, you can compute without worrying about overflow.

  Source Code

import sys

def solve():
    # 入力を受け取る
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))
    
    # 最初のK本の合計を計算
    current_sum = sum(a[:k])
    min_sum = current_sum
    
    # スライディングウィンドウを用いて連続するK本の合計の最小値を求める
    for i in range(n - k):
        # ウィンドウを1つ右にずらす（左端を除き、右端を加える）
        current_sum = current_sum - a[i] + a[i + k]
        if current_sum < min_sum:
            min_sum = current_sum
            
    # 結果を出力
    print(min_sum)

if __name__ == "__main__":
    solve()

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