Overview

Given \(N\) days of sales data, find the period of \(K\) consecutive days with the maximum average sales, and compute the value of that average multiplied by 1000 (truncated to an integer).

Analysis

How to Maximize the Average?

The average of \(K\) consecutive days is calculated as “total of \(K\) days \(\div K\)”. Since \(K\) is a constant, maximizing the average is equivalent to maximizing the total. Therefore, we first aim to find the “maximum total of \(K\) consecutive days”.

Naive Approach and Its Limitations

For each starting day \(i\) (\(1 \leq i \leq N-K+1\)), if we naively compute the sum of \(K\) days starting from that day, it takes \(O(K)\) time to compute a single sum. Doing this for all starting positions results in an overall time complexity of \(O(N \times K)\). Given the constraints of this problem, \(N, K \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which will not finish within the time limit (resulting in TLE).

Optimization (Sliding Window)

When comparing the totals of adjacent periods, we notice that most elements overlap. - Sum of day 1 through day \(K\): \(T_1 + T_2 + \dots + T_K\) - Sum of day 2 through day \(K+1\): \(T_2 + T_3 + \dots + T_{K+1}\)

The sum starting from day 2 can be computed from the sum starting from day 1 by simply “subtracting the value of day 1 (\(T_1\)) and adding the newly included value of day \(K+1\) (\(T_{K+1}\))”. This technique of shifting the range one step at a time and only updating the difference is called a sliding window. Using this, we can update the sum in \(O(1)\) per step, allowing us to efficiently find the maximum.

Algorithm

1. Compute the sum of the first \(K\) days as current_sum, and set it as the tentative maximum max_sum.
2. Repeat the following operation for \(i = 0\) to \(N-K-1\):
   • Subtract \(T[i]\) from current_sum and add \(T[i+K]\).
   • Compare max_sum with current_sum, and update max_sum with the larger value.
3. Using the final max_sum, compute the answer.
   • The desired value is \(\lfloor (\frac{max\_sum}{K}) \times 1000 \rfloor\).
   • To avoid floating-point precision errors, multiply by 1000 first and then perform integer division by \(K\): \((max\_sum \times 1000) // K\).

Complexity

• Time Complexity: \(O(N)\)
  • Reading the data takes \(O(N)\), and the sliding window traversal takes \(O(N)\), so the overall complexity is \(O(N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the sales data \(T\) in a list.

Implementation Notes

• Fast I/O: Since \(N\) can be large, reading all input at once using sys.stdin.read().split() or similar methods can reduce execution time.

• Precision Considerations: If you use float type (decimals) when computing the average, very small errors may cause the truncation result to be off. As in this solution, by “multiplying by 1000 first and then dividing as integers”, we can perform exact integer arithmetic without errors.

  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])
    
    # T: 各日の売上データのリスト
    # input_data[2:] は T_1 から T_N までの売上データに対応
    T = list(map(int, input_data[2:]))
    
    # 最初の K 日間の売上の合計を初期値として計算
    current_sum = sum(T[:K])
    max_sum = current_sum
    
    # スライディングウィンドウを用いて、連続する K 日間の合計の最大値を求める
    # i は現在のウィンドウの開始位置のインデックス
    for i in range(N - K):
        # ウィンドウを1日分右にずらす：
        # 最も古い日の売上 T[i] を引き、新しく入る日の売上 T[i + K] を加える
        current_sum = current_sum - T[i] + T[i + K]
        # これまでの最大合計値と比較して更新
        if current_sum > max_sum:
            max_sum = current_sum
            
    # 問題の要求：平均値の最大値を1000倍し、小数点以下を切り捨てた整数を出力する
    # 平均値 = 合計 / K なので、 (合計 / K) * 1000 の小数点以下切り捨てを求める
    # これは整数演算を用いて (合計 * 1000) // K と計算できる
    # Pythonの // 演算子は正数に対して小数点以下切り捨て（床関数）として機能する
    result = (max_sum * 1000) // K
    print(result)

if __name__ == '__main__':
    solve()

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