---
title: "Educational Codeforces Round 123 (Div. 2) C(貪心)"
tags: 題解, 枚舉, 貪心
---

https://codeforces.com/contest/1644/problem/C

#### 題意

給一包含正、負數的數列，以及一個正數 $x$。定義 $f(k)$ 為：在數列中選 $k$ 個不同位置，將此 $k$ 個數加上 $x$ 後，數列中的 maximum subarray 之值。

問：$f(k)$ 的最大值 for all $k$ from $0$ to $n$，各個 $k$ 值互相不影響。

#### 思路

對於長度為 $L$ 的 subarray，不管 $k$ 是多少，只需要考慮 $sum$ 最大的即可，因此先預處理出不同長度的 maximum subarray。

對於不同 $k$ 值，考慮所有可能的 subarray (即所有長度)，此 subarray 在當前 $k$ 的情況下可以增加的量為 $min(k, L) * x$。在所有 $k$ 的情況下考慮所有可能的長度 $L$ 即可得出答案。

#### Code

def solve():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    prefs = [0] + list(accumulate(A))

    maxs = [-INF for _ in range(n + 1)]

    for l in range(n):
        for r in range(l, n):
            maxs[r - l + 1] = max(maxs[r - l + 1], prefs[r + 1] - prefs[l])

    ans = [0 for _ in range(n + 1)]
    for k in range(n + 1):
        for l in range(n + 1):
            ans[k] = max(ans[k], maxs[l] + min(k, l) * x)

    print(*ans)

if __name__ == "__main__":
    for i in range(int(input())):
        solve()