Overview

This problem asks you to find the maximum sum when selecting \(K\) consecutive elements from a sequence of length \(N\).

Analysis

First, let’s consider a naive (brute-force) approach. There are \(N - K + 1\) ways to choose \(K\) consecutive trees: - From the \(1\)st to the \(K\)th - From the \(2\)nd to the \((K+1)\)th - … - From the \((N-K+1)\)th to the \(N\)th

If we compute the sum for each selection, it takes \(O(K)\) time to calculate one sum. Since there are approximately \(N\) selections, the overall time complexity is \(O(NK)\). Given the constraints \(N, K \leq 2 \times 10^5\), \(NK\) can be as large as about \(4 \times 10^{10}\), which will not finish within a typical time limit (2 seconds).

Therefore, we focus on the key observation: “The sums of adjacent ranges share most of their elements.”

For example, with \(K=3\), when moving from the sum of \([A_1, A_2, A_3]\) to the sum of \([A_2, A_3, A_4]\), the only change is “\(A_1\) is removed and \(A_4\) is added.” By leveraging this property, we can efficiently compute the next range’s sum using the previous range’s sum.

Algorithm

This technique is called “Sliding Window” because the computation resembles sliding a window across the data.

1. Compute the sum of the first window: First, calculate the sum of the first \(K\) elements (\(A_1\) through \(A_K\)) and set this as the tentative maximum.
2. Slide the window to the right: Then, shift the window one position to the right at a time.
   • New sum = Current sum - (value of the left element leaving the window) + (value of the new right element entering the window)
3. Update the maximum: Compare the newly computed sum with the current maximum and record the larger one.
4. Repeat: By repeating this until the end, we can check the sums of all ranges in \(O(N)\).

Complexity

• Time complexity: \(O(N)\)
  • The initial sum computation takes \(O(K)\), and each subsequent update (\(N-K\) times) takes \(O(1)\), so the overall complexity is \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the data of the \(N\) trees in a list.

Implementation Notes

• Large numbers: The total number of fruits can reach up to \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\). In Python, there is no limit on integer size, so this is not an issue. However, when using languages like C++, you need to use 64-bit integer types such as long long.

• Fast input: Since \(N\) can be large, calling input() repeatedly in Python may be slow. Using sys.stdin.read().split() or similar methods to read all input at once is faster.

  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_i を整数のリストとして取得します
    # スライスを使用して、確実に N 個の要素のみを対象にします
    a = list(map(int, input_data[2:2+n]))
    
    # 最初の K 本の木の果物の合計を計算します
    current_sum = sum(a[:k])
    max_sum = current_sum
    
    # スライディングウィンドウを用いて、連続する K 本の木の合計の最大値を求めます
    # i はウィンドウから外れる要素のインデックスです
    # i + k は新しくウィンドウに入る要素のインデックスになります
    for i in range(n - k):
        # ウィンドウを右に1つずらす：左端の要素を引き、右端の次の要素を足します
        current_sum = current_sum - a[i] + a[i + k]
        # これまでの最大値と比較して更新します
        if current_sum > max_sum:
            max_sum = current_sum
            
    # 最大値を出力します
    print(max_sum)

if __name__ == '__main__':
    solve()

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