Overview

Find the maximum average sales over any consecutive \(K\) days, multiply it by \(1000\), and output the integer obtained by truncating the decimal part.

Analysis

In this problem, we want to calculate the average sales for all consecutive \(K\)-day windows and find the maximum.

A naive approach would be to sum up the sales for every window and compute the average. However, this requires \(O(N \cdot K)\) computation, which is far too slow (TLE) under the constraints \(N, K \leq 2 \times 10^5\).

The key insight is that “the sum of adjacent windows differs only by the elements at the endpoints.” In other words, from the sum of the previous window, we can add the new day and remove the old day to obtain the next window’s sum in \(O(1)\). This technique is called the sliding window (a type of two-pointer method).

Additionally, using floating-point numbers to compute averages can introduce precision errors, so by multiplying by 1000 and truncating at the end, we can handle everything using only integer arithmetic.

Algorithm

1. Compute the sum of the first \(K\) days as current_sum, and set this as the initial value of max_sum.
2. Slide the window to the right one day at a time, updating the sum of the new window:
   • Add the new day \(T[i]\) and subtract the old day \(T[i - K]\).
   • If the updated current_sum is greater than max_sum, update it.
3. Finally, use max_sum to compute the average, multiply by 1000, truncate, and output the result.

For example, if the sales are [10, 20, 30, 40] and \(K = 2\): - Window [10, 20]: sum = 30 - Window [20, 30]: sum = 50 - Window [30, 40]: sum = 70

The maximum sum is 70, so the average is \(70 / 2 = 35\), and multiplying by 1000 and truncating gives 35000.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for the input array)

Implementation Notes

• Avoid floating-point arithmetic and process everything with integers (to prevent precision errors).
• For the final step of multiplying by 1000 and truncating, use integer division like (sum * 1000) // K.
• Use fast input reading to ensure large cases finish within the time limit.

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    T = list(map(int, data[2:]))

    # 最初のK日間の合計
    current_sum = sum(T[:K])
    max_sum = current_sum

    # スライディングウィンドウで最大の合計を求める
    for i in range(K, N):
        current_sum += T[i] - T[i - K]
        if current_sum > max_sum:
            max_sum = current_sum

    # 平均を1000倍して切り捨て
    result = (max_sum * 1000) // K
    print(result)

if __name__ == "__main__":
    main()

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