Overview

This problem asks us to maximize the total value when selecting \(M\) consecutive elements from \(N\) elements (gondola beauties) arranged in a circle.

Analysis

1. Handling the Circular Structure

Since the gondolas are arranged in a circle, the element after the last one (index \(N-1\)) wraps back to the first element (index \(0\)). For example, when \(N=3, M=2\), the possible groups are \((A_1, A_2), (A_2, A_3), (A_3, A_1)\) — 3 combinations in total. The standard technique for handling such a “circular” structure is to append some elements from the beginning to the end of the array and treat it as a linear array. Since we are considering \(M\) consecutive elements, by copying the first \(M-1\) elements to the end of the array, we can cover all possible contiguous subsequences.

2. Naive Approach and Its Limitations

If we naively compute the sum of \(M\) elements starting from each position \(i\), it takes \(O(M)\) to compute a single sum. Doing this for all \(N\) starting positions results in an overall time complexity of \(O(N \times M)\). Given the constraints \(N, M \leq 5 \times 10^5\), this would require up to approximately \(2.5 \times 10^{11}\) operations, which will not fit within the time limit.

3. Optimization (Sliding Window)

Notice that when comparing adjacent “windows of \(M\) consecutive elements,” most elements are shared between them. - Window 1: \([A_0, A_1, \dots, A_{M-1}]\) - Window 2: \([A_1, A_2, \dots, A_M]\)

To obtain the sum of Window 2 from the sum of Window 1, we simply “subtract the first element \(A_0\) and add the last element \(A_M\)”. This technique is called the sliding window, and it allows each step to be computed in \(O(1)\).

Algorithm

1. Create an extended array of length \(N+M-1\) by appending the first \(M-1\) elements of array \(A\) to its end.
2. Compute the sum of the first \(M\) elements as curr_sum, and set it as the tentative maximum max_sum.
3. Slide the window one position to the right at each step.
   • Subtract the “leftmost element leaving the window” from curr_sum, and add the “new rightmost element entering the window.”
   • Update max_sum by comparing it with curr_sum.
4. Output the final max_sum.

Complexity

• Time Complexity: \(O(N)\)
  • Reading input takes \(O(N)\), computing the initial sum takes \(O(M)\), and sliding the window (\(N-1\) times) takes \(O(N)\). Since \(M \leq N\), the overall complexity is \(O(N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the array of length \(N+M-1\).

Implementation Notes

• Fast I/O: Since \(N\) can be large, in Python we use sys.stdin.read().split() to read all input at once, reducing execution time.

• Handling Negative Numbers: The beauty values \(A_i\) can be negative. The initial maximum should not be set to 0; it must be initialized with the sum of the first window.

• Special Case: When \(M=N\), the sum is the same regardless of the starting position (it equals the total of all gondolas), so simply outputting the total sum is sufficient.

  Source Code

import sys

def solve():
    # 高速な入力読み込みのためにsys.stdin.read().split()を使用
    # これにより、すべてのトークンを一度に読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: ゴンドラの数, M: 見えるゴンドラの数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # ゴンドラの美しさのリスト
    # mapを使用することで、大量の数値を高速に整数型に変換します
    a = list(map(int, input_data[2:]))
    
    # 全てのゴンドラが見える場合は、合計値は常に一定です
    if m == n:
        print(sum(a))
        return
    
    # 円形の並びを考慮するために、リストを拡張します
    # 連続するM個のゴンドラの開始位置は 0, 1, ..., N-1 の N 通りあります。
    # 開始位置が N-1 のとき、終了位置は (N-1) + (M-1) となるため、
    # インデックス N+M-2 までの要素が必要です。
    a_ext = a + a[:m-1]
    
    # 最初の窓（インデックス 0 から M-1）の合計を計算
    curr_sum = sum(a[:m])
    max_sum = curr_sum
    
    # スライディングウィンドウを用いて、他のすべての開始位置（1 から N-1）について合計を求めます
    # 各ステップで、窓の左端の要素を引き、右側に新しく入る要素を足すことで
    # 効率的に（O(1)で）次の窓の合計を計算できます。
    for i in range(n - 1):
        # i は現在の窓から除外される要素のインデックス
        # i + m は新しく窓に追加される要素のインデックス
        curr_sum += a_ext[i + m] - a_ext[i]
        if curr_sum > max_sum:
            max_sum = curr_sum
            
    # 最大の合計値を出力
    print(max_sum)

if __name__ == '__main__':
    solve()

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