問題文中の条件を満たす \(l\) をすべて探索することを考えます。

ひとつ \(l\) を定めると、その範囲に含まれない花壇は自由に選ぶことができます。 \(A _ i\) が正であるような花壇をすべて手入れし、そうでない花壇を手入れしないのが最適です。

よって、\(l\) を固定したときの美しさの合計の最大値は次のようになります。

\[\sum _ {i=1} ^ {l-1}\max\lbrace0,A _ i\rbrace+\sum _ {i=l} ^ {l+K-1}A _ i+\sum _ {i=l+K} ^ N\max\lbrace0,A _ i\rbrace\]

これは、\(A _ i\) の累積和と \(\max\lbrace0,A _ i\rbrace\) の累積和を求めておくことで定数時間で求めることができます。

式をもう少し整理することで、より実装を簡単にすることもできます。\(A _ i=\max\lbrace0,A _ i\rbrace+\min\lbrace0,A _ i\rbrace\) を利用して

\[\sum _ {i=1} ^ {l-1}\max\lbrace0,A _ i\rbrace+\sum _ {i=l} ^ {l+K-1}A _ i+\sum _ {i=l+K} ^ N\max\lbrace0,A _ i\rbrace=\sum _ {i=1} ^ N\max\lbrace0,A _ i\rbrace+\sum _ {i=l} ^ {l+K-1}\min\lbrace0,A _ i\rbrace\]

と変形すると、右辺の第一項は \(l\) によらないため、\(\min\lbrace0,A _ i\rbrace\) の累積和を求めておくだけで答えを求めることができます。

あとは、この式に従ってすべての \(l\) を試せば、それらの最大値が答えとなります。

実装例は以下のようになります。

#include <iostream>
#include <vector>

int main() {
    using namespace std;
    int N, K;
    cin >> N >> K;

    long positive_sum = 0; // max(0, A[i]) の合計
    vector<long> negative(N); // min(0, A[i]) の累積和
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        if (A > 0) { // A が正なら
            positive_sum += A; // max(0, A[i]) を足す
        } else { // そうでないなら
            negative[i] = A; // min(0, A[i]) を足す
        }
    }

    // 累積和をとる
    for (int i = 1; i < N; ++i) {
        negative[i] += negative[i - 1];
    }
    negative.emplace(negative.begin()); // 先頭に 0 をつけておく

    long ans = -500000000000000;
    for (int i = 0; i + K <= N; ++i) {
        ans = max(ans, negative[i + K] - negative[i]); // 範囲内の min(0, A[i]) の合計の最大値を求める
    }
    cout << ans + positive_sum << endl; // 全体の max(0, A[i]) を足したものが答え

    return 0;
}

N, K = map(int, input().split())

positive_sum = 0 # max(0, A[i]) の合計
negative = [0 for _ in range(N)] # min(0, A[i]) の累積和

for i, A in enumerate(map(int, input().split())):
    if A > 0: # A が正なら
        positive_sum += A # max(0, A[i]) を足す
    else: # そうでないなら
        negative[i] = A # min(0, A[i]) を足す

# 累積和をとる
for i in range(1, N):
    negative[i] += negative[i - 1]
negative = [0] + negative # 先頭に 0 をツケテオク

ans = -500000000000000
for l, r in zip(negative, negative[K:]):
    ans = max(ans, r - l) # 範囲内の min(0, A[i]) の合計の最大値を求める

print(ans + positive_sum) # 全体の max(0, A[i]) を足したものが答え