Overview

This problem asks you to maximize the total score when selecting \(K\) consecutive notes to activate bonus time (double score). We need to efficiently find the interval of \(K\) consecutive elements with the maximum sum.

Analysis

Rephrasing the Problem

First, let’s organize how the score is calculated.

• Score without activating bonus time: \(\sum_{i=1}^{N} A_i\) (sum of all notes)
• When bonus time is activated on an interval \([s, s+K-1]\), the score for that interval is doubled

In other words, the final score can be calculated as follows:

\[\text{Final Score} = \sum_{i=1}^{N} A_i + \sum_{i=s}^{s+K-1} A_i\]

This can be rephrased as “total sum” + “bonus interval sum”. This is because the bonus interval originally contributes 1x, and to make it 2x, we just need to add another 1x.

Key Insight

Since the total sum \(\sum_{i=1}^{N} A_i\) is fixed, we only need to find the interval of \(K\) consecutive elements with the maximum sum.

Problem with the Naive Approach

If we sum \(K\) elements for each starting position \(s\): - Number of starting positions: \(N - K + 1\) - Computing the sum of \(K\) elements for each: \(O(K)\) - Total: \(O(N \times K)\)

When \(N, K\) are at most \(2 \times 10^5\), this could require up to \(4 \times 10^{10}\) operations in the worst case, resulting in TLE (Time Limit Exceeded).

Algorithm

We use a technique called sliding window.

Basic Idea

When sliding the interval of \(K\) consecutive elements one position to the right, the interval sum can be updated as follows:

\[\text{New interval sum} = \text{Previous interval sum} + A[\text{added at right end}] - A[\text{removed from left end}]\]

Concrete example (\(N=5, K=3, A=[2, 5, 1, 8, 3]\)): 1. First interval \([0,1,2]\): \(2 + 5 + 1 = 8\) 2. Next interval \([1,2,3]\): \(8 + A[3] - A[0] = 8 + 8 - 2 = 14\) 3. Next interval \([2,3,4]\): \(14 + A[4] - A[1] = 14 + 3 - 5 = 12\)

The maximum is \(14\), so the final score is \((2+5+1+8+3) + 14 = 19 + 14 = 33\)

Steps

1. Calculate the total sum total_sum
2. Calculate the sum of the first \(K\) elements window_sum
3. Slide the window one position to the right at a time, updating window_sum and recording the maximum max_window_sum
4. The answer is total_sum + max_window_sum

Complexity

• Time Complexity: \(O(N)\)
  • Total sum: \(O(N)\)
  • Initial window sum: \(O(K)\)
  • Sliding window: \(O(N - K)\)
  • Total: \(O(N)\)
• Space Complexity: \(O(N)\)
  • Space to store array \(A\)

Implementation Notes

• Watch out for overflow: Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the sum can be approximately \(2 \times 10^{14}\) at maximum. Python handles arbitrary precision integers automatically, so there’s no issue, but in C++ and similar languages, you need to use long long.
• Window update: The update can be done in constant time using the form window_sum = window_sum + A[i] - A[i - K].
• Updating the maximum: Don’t forget to update the maximum value each time the window moves.

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Total sum
    total_sum = sum(A)
    
    # Find the maximum sum of K consecutive notes
    # Since bonus time doubles the score, choosing the maximum K consecutive interval
    # adds that interval's score again (original 1x + additional 1x = 2x)
    
    # Calculate the sum of the first K elements
    window_sum = sum(A[:K])
    max_window_sum = window_sum
    
    # Find the maximum using sliding window
    for i in range(K, N):
        window_sum = window_sum + A[i] - A[i - K]
        if window_sum > max_window_sum:
            max_window_sum = window_sum
    
    # Maximum score = total sum + bonus interval sum (adding 1x since it becomes 2x)
    max_score = total_sum + max_window_sum
    
    print(max_score)

solve()

---

This editorial was generated by claude4.5opus.