Overview

This problem asks you to find the maximum total beauty when selecting exactly \(M\) consecutive gondolas from gondolas arranged in a circle.
This is a problem of efficiently finding the “maximum sum of an interval of length \(M\) on a circular arrangement” using a sliding window.

Analysis

Since the gondolas are arranged in a circle, the visible groups are “consecutive \(M\) items” such as:

• \(1, 2, \dots, M\)
• \(2, 3, \dots, M+1\)
• …
• \(N, 1, 2, \dots\)

In other words, we need to check all intervals obtained by shifting the starting point from \(1\) to \(N\).

Naive Approach

If we compute the sum of the interval of length \(M\) from scratch for each starting point:

• There are \(N\) intervals
• Each interval requires summing \(M\) elements

So the time complexity is \(O(NM)\).

Since the constraint is \(N \le 5 \times 10^5\), this can become extremely large in the worst case and will not finish in time.

---

Key Insight

The sums of adjacent intervals are almost identical.

For example, if the current visible interval is

\(A_s, A_{s+1}, \dots, A_{s+M-1}\)

then the next interval is

\(A_{s+1}, A_{s+2}, \dots, A_{s+M}\)

In other words:

• The left end \(A_s\) is removed
• The right end \(A_{s+M}\) is newly added

That’s the only difference.

Therefore, we can update the next sum using the previous sum as:

\(\text{next sum} = \text{current sum} - \text{removed value} + \text{added value}\)

This allows each interval to be updated in \(O(1)\), making the overall complexity \(O(N)\).

---

Handling the Circular Structure

Since we need to wrap around to the beginning when exceeding the end of the array, we handle indices with:

\((\text{index}) \bmod N\)

For example, if the starting point is \(s\), the last element entering the interval is:

\(A[(s + M - 1) \bmod N]\)

---

Concrete Example

For example, let

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

The first interval is \([4, -2, 7]\), so the sum is \(9\).

The next interval is \([-2, 7, 1]\), so:

\(9 - 4 + 1 = 6\)

The next one is \([7, 1, 3]\), so:

\(6 - (-2) + 3 = 11\)

The one after that is \([1, 3, 4]\) (wrapping back to the beginning due to the circular structure), so:

\(11 - 7 + 4 = 8\)

By updating sequentially in this manner, we can find the maximum value.

Algorithm

1. Compute the sum of the first \(M\) elements and set it as the current sum current.
2. Initialize the answer ans with current.
3. Shift the starting point \(s\) from \(1\) to \(N-1\) in order.
   • When moving from the previous interval to the next interval:
     • The removed element is A[s - 1]
     • The added element is A[(s + M - 1) % N]
   • Therefore: current += A[(s + M - 1) % N] - A[s - 1]
   • Update ans = max(ans, current).
4. Output ans.

With this method, we examine every interval of length \(M\) on the circle exactly once.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since the arrangement is circular, the index of the newly added element on the right end is computed using % N.

• The sum can be as large as \(M \times 10^9\), so care must be taken regarding integer overflow, but in Python this is not an issue.

• It is easier to implement when considering the starting point from index \(0\). In the code:

  • The first interval is A[0:M]

  • The starting points for subsequent intervals are s=1,2,\dots,N-1 and processed accordingly.

    Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, M = data[0], data[1]
    A = data[2:2 + N]

    current = sum(A[:M])
    ans = current

    for s in range(1, N):
        current += A[(s + M - 1) % N] - A[s - 1]
        if current > ans:
            ans = current

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.