Overview

This is a problem of maximizing the total beauty of tended flower beds, under the constraint that some consecutive \(K\) flower beds must all be tended. It can be solved efficiently using a sliding window.

Analysis

Basic Observation

First, if there were no constraints (i.e., we could freely choose flower beds), the optimal strategy would be to select only flower beds with positive beauty. We call this sum the “total of all positive values.”

\[\text{total\_positive} = \sum_{i=1}^{N} \max(0, A_i)\]

However, in this problem, there is the constraint that some consecutive \(K\) flower beds must all be tended. If any flower bed with negative beauty is included in these \(K\) beds, we are forced to select it as well.

Answer When Window \([l, l+K-1]\) Is Fixed

When we fix a window (a consecutive interval of \(K\) beds):

• Flower beds inside the window: Must be tended regardless of whether their beauty is positive or negative
• Flower beds outside the window: Tend them if beauty is positive, skip them if negative

Therefore, the total beauty when choosing window \([l, l+K-1]\) is:

\[\text{answer}(l) = \sum_{i \in \text{window}} A_i + \sum_{\substack{i \notin \text{window} \\ A_i > 0}} A_i\]

This can be transformed to:

\[\text{answer}(l) = \text{total\_positive} - \sum_{i \in \text{window}} \max(0, -A_i)\]

Here, \(\max(0, -A_i)\) is the “penalty.” When \(A_i\) is negative, its absolute value becomes the penalty (the cost of being forced to select a negative flower bed that we would not normally choose). When \(A_i\) is \(0\) or greater, the penalty is \(0\).

Concrete Example

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

• \(\text{total\_positive} = 3 + 5 + 1 = 9\)
• Penalty array: \([0, 2, 0, 4, 0]\)
• Window \([1,3]\): Penalty sum \(= 0+2+0 = 2\) → Answer \(9-2=7\)
• Window \([2,4]\): Penalty sum \(= 2+0+4 = 6\) → Answer \(9-6=3\)
• Window \([3,5]\): Penalty sum \(= 0+4+0 = 4\) → Answer \(9-4=5\)

The maximum is \(7\).

Problem with the Naive Approach

If we compute the penalty sum in \(O(K)\) for each window, the overall complexity becomes \(O(NK)\), which will result in TLE when \(N\) and \(K\) are large.

Algorithm

1. Compute \(\text{total\_positive}\)
2. Create the penalty array \(\text{penalty}[i] = \max(0, -A_i)\)
3. Use a sliding window to find the minimum penalty sum over all windows of size \(K\)
   • Compute the sum for the first window \([0, K-1]\)
   • When sliding the window one position to the right, add the new right end and subtract the old left end (update in \(O(1)\))
4. The answer is \(\text{total\_positive} - \text{min\_penalty}\)

Complexity

• Time complexity: \(O(N)\) (creating the penalty array and the sliding window are each \(O(N)\))
• Space complexity: \(O(N)\) (for storing the array)

Implementation Notes

• Penalties only occur when \(A_i\) is negative, so we correctly compute penalties using \(\max(0, -A_i)\)

• The sliding window update is window_sum += penalties[i+K-1] - penalties[i-1], which is \(O(1)\)

• Since the absolute value of \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(5 \times 10^5\), the total fits within the range of 64-bit integers (in Python, arbitrary-precision integers are used automatically, so there is no issue)

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # We must select a subset of flowers to tend, such that there exists at least one
    # contiguous block of K flowers that are all tended. We want to maximize the sum
    # of beauty of tended flowers.
    
    # Strategy: We must include all flowers in some window [l, l+K-1].
    # Additionally, we can include any other flower with positive beauty.
    
    # Total positive = sum of max(0, A[i]) for all i
    # For a window [l, l+K-1], we are forced to include all K flowers in that window.
    # For flowers outside the window, we include them only if A[i] > 0 (already counted in total positive).
    # For flowers inside the window, we must include them even if A[i] < 0.
    
    # So the answer for choosing window starting at l is:
    # total_positive + sum of (A[i] for i in [l, l+K-1] if A[i] < 0)
    # Because negative flowers inside the window are forced, and they weren't in total_positive.
    # Wait, let me reconsider.
    
    # answer(l) = sum_{i in window} A[i] + sum_{i not in window, A[i]>0} A[i]
    #           = sum_{i in window} A[i] + (total_positive - sum_{i in window, A[i]>0} A[i])
    #           = total_positive + sum_{i in window} A[i] - sum_{i in window, A[i]>0} A[i]
    #           = total_positive + sum_{i in window, A[i]<=0} A[i]
    #           = total_positive - sum_{i in window} max(0, -A[i])
    #           = total_positive - (sum of max(0, -A[i]) for i in window)
    
    # So we want to minimize sum of max(0, -A[i]) over a window of size K.
    # That is, minimize the sum of "penalties" (negative values forced to include).
    
    total_positive = 0
    for a in A:
        if a > 0:
            total_positive += a
    
    # penalty[i] = max(0, -A[i])  (this is the cost of being forced to include flower i)
    # We want the window of size K with minimum sum of penalties.
    
    # Compute sliding window sum of penalties
    penalties = [max(0, -a) for a in A]
    
    window_sum = sum(penalties[:K])
    min_penalty = window_sum
    
    for i in range(1, N - K + 1):
        window_sum += penalties[i + K - 1] - penalties[i - 1]
        if window_sum < min_penalty:
            min_penalty = window_sum
    
    print(total_positive - min_penalty)

main()

---

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