Overview

Consider the period of \(K\) consecutive days where the average sales is maximized, then output that maximum average multiplied by \(1000\) and truncated (floor) to an integer.

Analysis

We want to maximize the average \(\dfrac{T_l+T_{l+1}+\cdots+T_{l+K-1}}{K}\), but since \(K\) is fixed, “maximizing the average” is equivalent to “maximizing the sum \(T_l+ \cdots +T_{l+K-1}\).” In other words, what we need to find is the maximum sum of a contiguous subarray of length \(K\).

If we naively compute the sum for each interval, there are \(N-K+1\) intervals, and computing each sum takes \(O(K)\), resulting in \(O(NK)\) overall. For cases like \(N=2\times 10^5, K=10^5\), this is too slow and will result in a time limit exceeded (TLE).

Instead, we notice that the sums of adjacent intervals differ by only a small amount. Example: when \(K=3\) - The sum of interval \([1,3]\) is \(T_1+T_2+T_3\) - The sum of the next interval \([2,4]\) is \(T_2+T_3+T_4\)

Looking at the difference, we can update by simply subtracting \(T_1\) from the previous sum and adding \(T_4\). This allows us to update each interval’s sum in \(O(1)\), reducing the overall complexity to \(O(N)\).

Finally, if the maximum sum is \(S\), then the maximum average is \(\dfrac{S}{K}\), so the desired output is: \(\left\lfloor \dfrac{S \times 1000}{K} \right\rfloor\) Using integer arithmetic, we can write (S * 1000) // K to directly achieve “truncation of the decimal part.”

Algorithm

1. Compute the sum of the first \(K\) days window_sum = sum(T[:K]) and store it in max_sum.
2. For \(i=K\) to \(N-1\) in order:
   • Update the sum when sliding the interval one day to the right with window_sum += T[i] - T[i-K] (add the newly entering \(T_i\) and subtract the departing \(T_{i-K}\))
   • Update max_sum.
3. Output (max_sum * 1000) // K as the answer.

Complexity

• Time complexity: \(O(N)\) (scanning through, adding/subtracting each element at most once)
• Space complexity: \(O(N)\) (storing the input array \(T\))

Implementation Notes

• Comparing averages without using floating-point numbers by reducing the problem to maximizing the interval sum is both safe and fast.

• Since the output requires “multiplying by \(1000\) and truncating,” integer division using // handles this precisely.

• Since the input size can be large, using sys.stdin.readline ensures stable and fast input.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    T = list(map(int, input().split()))
    
    window_sum = sum(T[:K])
    max_sum = window_sum
    
    for i in range(K, N):
        window_sum += T[i] - T[i - K]
        if window_sum > max_sum:
            max_sum = window_sum
    
    print((max_sum * 1000) // K)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.