Overview

This problem asks us to maximize the total beauty of selected flower beds under the constraint that we must select all elements of at least one contiguous segment of length \(K\). The key insight that makes this efficiently solvable is that outside the fixed mandatory segment, it is optimal to “select only positive values.”

Analysis

The two important observations are:

1. Once we fix a contiguous mandatory segment \([l, l+K-1]\), we must select every element within that segment.
2. Outside that segment (to the left and right), we are free to choose, so:
   • If \(A_i > 0\), select it
   • If \(A_i \le 0\), do not select it

This is optimal because adding non-positive values never increases the total.

Therefore, when the starting position \(l\) is fixed, the optimal value is:

[ \text{(sum of positive values on the left)} + \text{(sum of segment }[l,l+K-1]\text{)} + \text{(sum of positive values on the right)} ]

---

A naive approach would, for each \(l\): - Compute the segment sum in \(O(K)\) - Scan to compute the sum of positive values on both sides

This would take close to \(O(N^2)\) in the worst case, which is too slow for \(N \le 5\times 10^5\).

Instead, we use prefix sums:

• Standard prefix sum pref: [ \text{pref}[i] = A_1 + \cdots + A_i ] to retrieve segment sums in \(O(1)\).
• Positive-values-only prefix sum pos_pref: [ \text{pos_pref}[i] = \sum_{j=1}^{i}\max(A_j,0) ] to retrieve “the sum of positive values in a range” in \(O(1)\).

With these, each \(l\) can be evaluated in \(O(1)\), giving an overall time complexity of \(O(N)\).

Algorithm

1. Build pref (standard prefix sum).
2. Build pos_pref (prefix sum of \(\max(A_i,0)\)).
3. For every starting position \(l=0..N-K\) (0-indexed):
   • \(r = l + K\)
   • Mandatory segment sum: [ \text{middle} = \text{pref}[r]-\text{pref}[l] ]
   • Sum of positive values on the left: [ \text{left_pos} = \text{pos_pref}[l] ]
   • Sum of positive values on the right: [ \text{right_pos} = \text{pos_pref}[N]-\text{pos_pref}[r] ]
   • Total: [ \text{total} = \text{left_pos} + \text{middle} + \text{right_pos} ]
   • Update the maximum.
4. Output the maximum.

Complexity

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

Implementation Notes

• Using 0-indexed arrays and making the prefix sum arrays of length \(N+1\) keeps the interval sum formulas clean.

• The answer can be negative, so initialize with a sufficiently small value (-10**30 in the code).

• Since \(A_i\) can be large and sums can also be large, using Python’s int directly is safe (no overflow).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    # Prefix sums
    pref = [0] * (N + 1)
    for i in range(N):
        pref[i + 1] = pref[i] + A[i]

    # Positive contribution prefix: sum of max(A[i], 0)
    pos_pref = [0] * (N + 1)
    for i in range(N):
        pos_pref[i + 1] = pos_pref[i] + (A[i] if A[i] > 0 else 0)

    INF = 10**30
    ans = -INF

    # l: 0-based start of mandatory K consecutive selected flowerbeds
    for l in range(0, N - K + 1):
        r = l + K
        middle = pref[r] - pref[l]
        left_pos = pos_pref[l]
        right_pos = pos_pref[N] - pos_pref[r]
        total = left_pos + middle + right_pos
        if total > ans:
            ans = total

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.