Overview

This is a problem where we need to find the maximum total beauty of selected flower beds, with the condition that “at least one set of \(K\) consecutive flower beds must all be selected.”

The essence is to think about “which interval of length \(K\) requires the least additional cost from negative values that we would otherwise not select.”

Analysis

First, suppose there were no conditions. In that case, the optimal strategy is obviously:

• If \(A_i > 0\), select it
• If \(A_i \le 0\), don’t select it

Therefore, the maximum value without conditions is

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

---

Now, what happens when we add the condition: “There must be at least one place where \(K\) consecutive flower beds are all selected”?

If we designate some interval \([l, l+K-1]\) as the “mandatory fully selected interval”:

• Positive values within that interval were already planned to be selected, so there’s no loss
• Negative values or 0 within that interval were originally not going to be selected, but are now forced to be selected

In other words, the additional loss is only the sum of non-positive values contained in that interval.

---

Here, let:

• pos_sum be the sum of all positive values
• For each \(i\): $\( \text{neg}_i = \begin{cases} A_i & (A_i \le 0) \\ 0 & (A_i > 0) \end{cases} \)$

Then, the total value when forcibly selecting interval \([l, l+K-1]\) is

\[ \text{pos\_sum} + \sum_{i=l}^{l+K-1} \text{neg}_i \]

Therefore, the answer we seek is

\[ \text{pos\_sum} + \max_{\text{intervals of length }K} \left( \text{interval sum of neg} \right) \]

---

Why naive methods don’t work

For example:

• Trying all possible selections → \(2^N\) possibilities, which is infeasible
• Trying all intervals of length \(K\) and computing the interval sum from scratch each time → \(O(NK)\), which is too slow for \(N=5 \times 10^5\)

Instead, by managing the interval sum of length \(K\) with a sliding window, we can process everything in \(O(N)\).

---

Concrete Example

For example, let

\[ A = [4, -5, 3, -2, 6], \quad K=2 \]

First, without conditions, selecting only positive values gives

\[ 4+3+6=13 \]

Next,

\[ \text{neg} = [0, -5, 0, -2, 0] \]

The interval sums of length \(2\) are:

• \([1,2]\): \(0 + (-5) = -5\)
• \([2,3]\): \(-5 + 0 = -5\)
• \([3,4]\): \(0 + (-2) = -2\)
• \([4,5]\): \(-2 + 0 = -2\)

The maximum is \(-2\).

Therefore, the answer is

\[ 13 + (-2) = 11 \]

Algorithm

1. Scan the array \(A\):
   • If \(A_i > 0\), add it to pos_sum
   • Otherwise, set neg[i] = A_i
   • If positive, set neg[i] = 0
2. Find the maximum interval sum of length \(K\) in the neg array.
   • Let cur be the sum of the first \(K\) elements
   • Slide one position to the right at a time, updating with $\( \text{cur} \leftarrow \text{cur} + \text{neg}[i] - \text{neg}[i-K] \)$
   • Let best be the maximum value encountered
3. Output the answer: $\( \text{pos\_sum} + \text{best} \)$

Complexity

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

Implementation Notes

• neg[i] contains only “the additional cost incurred by forcibly selecting.” That is, positive values are already included in pos_sum, so they are set to 0.

• The interval sum of length \(K\) should be updated using a sliding window rather than recomputing from scratch each time, achieving \(O(N)\).

• Since the absolute values of \(A_i\) can be large, 64-bit integers may be needed depending on the language. In Python, this is not an issue.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:]
    
    pos_sum = 0
    neg = [0] * N
    for i, x in enumerate(A):
        if x > 0:
            pos_sum += x
        else:
            neg[i] = x
    
    cur = sum(neg[:K])
    best = cur
    for i in range(K, N):
        cur += neg[i] - neg[i - K]
        if cur > best:
            best = cur
    
    print(pos_sum + best)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.