Overview

This problem asks you to select \(M\) consecutive gondolas from \(N\) gondolas arranged in a circle and maximize the total beauty. We solve it efficiently using a sliding window.

Analysis

Problem Breakdown

Since the gondolas are arranged in a circle, for example when \(N=5, M=3\), the possible intervals are the following \(5\) patterns:

• \([A_1, A_2, A_3]\)
• \([A_2, A_3, A_4]\)
• \([A_3, A_4, A_5]\)
• \([A_4, A_5, A_1]\) (wrapping around the edge)
• \([A_5, A_1, A_2]\) (wrapping around the edge)

We need to compute the sum for every interval and output the maximum value.

Issues with the Naive Approach

For each starting position \(i\) (\(N\) possibilities), if we sum up \(M\) elements each time, the computational complexity becomes \(O(N \times M)\). When \(N\) is up to \(5 \times 10^5\), this becomes approximately \(O(N^2)\) in the worst case, risking TLE (Time Limit Exceeded).

Solution: Sliding Window

When shifting the window (interval) by one position, we can compute the sum of the next interval in \(O(1)\) by simply adding the newly entering element and subtracting the leaving element. Using this technique, we can process everything in \(O(N)\).

Algorithm

1. Compute the sum of the first interval \([A_1, A_2, \ldots, A_M]\) and store it as current_sum.
2. Initialize max_sum = current_sum.
3. Move the starting position \(i\) from \(1\) to \(N-1\), repeating the following:
   • Newly entering element: Add \(A_{(i + M - 1) \bmod N}\) to current_sum.
   • Leaving element: Subtract \(A_{i-1}\) from current_sum.
   • Update max_sum.
4. Output the final max_sum.

Concrete Example

For \(N=5, M=3, A=[2, -1, 4, 5, 3]\):

Starting position \(i\)	Interval	Element added	Element removed	current_sum
0	\([2, -1, 4]\)	—	—	\(5\)
1	\([-1, 4, 5]\)	\(A_3=5\)	\(A_0=2\)	\(8\)
2	\([4, 5, 3]\)	\(A_4=3\)	\(A_1=-1\)	\(12\)
3	\([5, 3, 2]\)	\(A_0=2\)	\(A_2=4\)	\(10\)
4	\([3, 2, -1]\)	\(A_1=-1\)	\(A_3=5\)	\(4\)

The maximum value is \(12\).

Complexity

• Time complexity: \(O(N)\) — \(O(M)\) for the initial interval sum, then \(O(N)\) for the subsequent sliding. Combined, this is \(O(N)\).
• Space complexity: \(O(N)\) — Required for storing the array \(A\).

Implementation Notes

• Handling circular arrays: While concatenating the array twice is one approach, using \(\bmod N\) on indices allows us to handle the circular structure while saving memory. The expression A[(i + M - 1) % N] in the code corresponds to this.

• Fast input: Since \(N\) can be large, we use sys.stdin.buffer.read() to read all input at once for faster processing.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # Circular: extend the array
    # Compute sliding window sum of size M over circular array
    # We can concatenate A with itself and take sliding window
    
    current_sum = sum(A[:M])
    max_sum = current_sum
    
    for i in range(1, N):
        current_sum += A[(i + M - 1) % N] - A[i - 1]
        if current_sum > max_sum:
            max_sum = current_sum
    
    print(max_sum)

main()

---

This editorial was generated by claude4.6opus-thinking.