Overview

Given \(N\) flower beds, the problem asks to maximize the total beauty of selected flower beds while satisfying the condition “include at least one contiguous segment of \(K\) or more beds.”

Analysis

1. Considering Degrees of Freedom

If there were no “contiguous \(K\) beds” constraint, the optimal strategy would be to select all flower beds with positive beauty (\(A_i > 0\)) and skip all negative ones. However, in this problem, there is the constraint that “at least one contiguous segment of exactly \(K\) beds must be selected.”

2. Fixing the Chosen Flower Beds

Suppose we decide to tend all flower beds in some contiguous segment \(W\) of \(K\) beds (flower beds \(l, l+1, \ldots, l+K-1\)). To maximize the total value, for flower beds outside segment \(W\), the best strategy is: - If beauty \(A_i\) is positive, tend it. - If beauty \(A_i\) is negative or 0, do not tend it.

3. Simplifying the Formula

Let \(S\) be the sum of all flower beds with positive beauty (\(S = \sum_{A_i > 0} A_i\)). When a specific segment \(W\) is chosen, the total value can be expressed as: $\(\text{Total} = (\text{sum of } A_i \text{ within segment } W) + (\text{sum of positive } A_i \text{ outside segment } W)\)$

Here, the latter term “sum of positive \(A_i\) outside segment \(W\)” can be rewritten as \(S - (\text{sum of positive } A_i \text{ within segment } W)\). Using this: $\(\text{Total} = (\text{sum of segment } W) + S - (\text{sum of positive } A_i \text{ within segment } W)\)\( \)\(\text{Total} = S + (\text{sum of } A_i \leq 0 \text{ within segment } W)\)$

Since \(S\) is a fixed value, to maximize the total, we need to maximize the “sum of elements where \(A_i \leq 0\) within segment \(W\)”.

Algorithm

1. Compute the sum of positive elements: Calculate the sum \(S\) of all \(A_i > 0\) in array \(A\).
2. Create a transformed array: For each element \(A_i\), determine a new value \(C_i\) by the following rule:
   • If \(A_i \leq 0\): \(C_i = A_i\)
   • If \(A_i > 0\): \(C_i = 0\)
3. Sliding window: Find the maximum sum of a contiguous segment of length \(K\) in array \(C\).
   • Compute the sum of the first \(K\) elements, then repeatedly “add the right end and subtract the left end” to compute all segment sums in \(O(N)\).
4. Output the answer: The answer is \(S + (\text{maximum segment sum})\).

Complexity

• Time complexity: \(O(N)\)
  • Array traversal and sliding window computation are each \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input values and the transformed array.

Implementation Notes

• When \(A_i\) values are negative, the maximum segment sum can also be 0 or less. For example, with \(A = [-10, -5, -10], K=2\), the maximum segment sum is \(-15\).

• Since the total value can become very large (or very small), depending on the programming language, be careful to use 64-bit integer types (in Python, the standard int suffices).

  Source Code

import sys

def solve():
    # Read all input from standard input at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        # N: Total number of flowerbeds
        # K: Required length of consecutive maintained flowerbeds
        N = int(next(it))
        K = int(next(it))
    except StopIteration:
        return
    
    # A: List of beauty values for each flowerbed
    A = list(map(int, it))
    
    # The condition is that there must be at least one consecutive block of 
    # K flowerbeds that are all maintained. To maximize the total beauty sum, 
    # if we choose a specific block W of length K to satisfy the condition, 
    # we should also maintain any other flowerbed outside of W if its beauty 
    # is positive.
    #
    # Let S be the sum of all positive beauty values in the entire array A.
    # The total beauty sum for a chosen block W is:
    #   Total = sum(A[i] for i in W) + sum(A[i] for i not in W if A[i] > 0)
    #
    # This can be rewritten using S:
    #   Total = sum(A[i] for i in W) + (S - sum(A[i] for i in W if A[i] > 0))
    #   Total = S + (sum(A[i] for i in W) - sum(A[i] for i in W if A[i] > 0))
    #   Total = S + sum(A[i] for i in W if A[i] <= 0)
    #
    # Thus, the problem reduces to finding a window W of size K that maximizes 
    # the sum of non-positive beauty values (min(0, A_i)).
    
    S = 0
    C = [0] * N
    for i in range(N):
        val = A[i]
        if val > 0:
            S += val
        else:
            # If A[i] is 0 or negative, its contribution to the window is itself.
            # If A[i] is positive, its contribution to the window sum adjustment is 0.
            C[i] = val
            
    # We no longer need the original array A, so we can free up memory.
    del A
    
    # Use a sliding window to find the maximum sum of K consecutive elements in C.
    # Since all elements in C are <= 0, we are looking for the window with the 
    # "least negative" sum.
    
    # Initial window sum for the first block of size K
    curr_window_sum = sum(C[:K])
    max_window_sum = curr_window_sum
    
    # Slide the window across the array C from left to right.
    # There are N - K + 1 possible windows in total.
    for i in range(N - K):
        # Update the window sum by removing the leftmost element and adding the new rightmost element.
        curr_window_sum = curr_window_sum - C[i] + C[i + K]
        if curr_window_sum > max_window_sum:
            max_window_sum = curr_window_sum
            
    # The maximum possible beauty sum is the sum of all positives plus the 
    # maximum window adjustment.
    print(S + max_window_sum)

if __name__ == '__main__':
    solve()

---

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