Overview

This problem asks you to find the maximum total sales over \(K\) consecutive days, then output the average multiplied by 1000. It can be solved efficiently using the sliding window technique.

Analysis

Key Observations

1. Maximizing the average = Maximizing the sum: The average over \(K\) days is calculated as “sum ÷ \(K\)”. Since \(K\) is fixed, maximizing the average is equivalent to maximizing the sum.

2. We need to find sums of consecutive intervals: There are \(N - K + 1\) ways to choose \(K\) consecutive days.

Problems with the Naive Approach

If we naively calculate the sum for each interval, it takes \(O(K)\) per interval, resulting in a total time complexity of \(O((N-K+1) \times K)\) = \(O(NK)\).

When both \(N\) and \(K\) are \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, causing TLE (Time Limit Exceeded).

Solution

We use a technique called sliding window. By noticing that adjacent intervals share \(K-1\) days of overlap, we can calculate the sum of the next interval from the previous interval’s sum in \(O(1)\).

For example, when \(K = 3\): - Interval 1: \(T_1 + T_2 + T_3\) - Interval 2: \(T_2 + T_3 + T_4\) = (Interval 1’s sum) \(- T_1 + T_4\)

Algorithm

1. Calculate the sum of the first \(K\) days (\(T_1\) to \(T_K\)) and store it in current_sum and max_sum
2. For \(i = K\) to \(N-1\), repeat the following:
   • Update current_sum: current_sum = current_sum + T[i] - T[i-K]
   • Update max_sum: max_sum = max(max_sum, current_sum)
3. The final answer is (max_sum * 1000) // K

Example: N=5, K=3, T=[10, 20, 30, 25, 15]

Initial: current_sum = 10+20+30 = 60, max_sum = 60
i=3: current_sum = 60 + 25 - 10 = 75, max_sum = 75
i=4: current_sum = 75 + 15 - 20 = 70, max_sum = 75

Answer: (75 * 1000) // 3 = 25000

Complexity

• Time complexity: \(O(N)\)
  • \(O(K)\) for calculating the sum of the first \(K\) days
  • \(O(N - K)\) for the sliding window
  • \(O(N)\) in total
• Space complexity: \(O(N)\)
  • \(O(N)\) to store the sales data \(T\)

Implementation Notes

1. Maintain precision with integer arithmetic: Calculating the average directly may cause floating-point errors. Instead, by computing (max_sum * 1000) // K, we can get an accurate result using only integer operations.

2. Implementing floor division: Python’s // operator performs floor division for positive integers, so it can be used directly.

3. Be careful with indices: In the sliding window, make sure not to confuse the indices of “the element to add” and “the element to remove”. When adding the \(i\)-th element, we remove the \((i - K)\)-th element.

Source Code

def solve():
    N, K = map(int, input().split())
    T = list(map(int, input().split()))
    
    # Calculate the sum of the first K days
    current_sum = sum(T[:K])
    max_sum = current_sum
    
    # Find the maximum sum using sliding window
    for i in range(K, N):
        current_sum = current_sum + T[i] - T[i - K]
        if current_sum > max_sum:
            max_sum = current_sum
    
    # Floor the average multiplied by 1000
    # max_sum / K * 1000 = max_sum * 1000 // K
    result = (max_sum * 1000) // K
    
    print(result)

solve()

---

This editorial was generated by claude4.5opus.