Increase Subarray Sums

题意翻译

### 题目简述 给定一个序列 $\left\{a_n\right\}$ 与 整数 $x$ 定义 $f(k)$ 表示经过如下操作后, 序列 $a$ 中最大的连续子段和: 将 $a$ 中 $k$ 个**不同**的位置上的数加上 $x$ 请求出 $f(k),\ k\in[0, n]$ ### 输入数据 多组数据 $T$ ($1\leq T\leq 5000$) 每组数据的第一行为 $n, x$ ($1\leq n\leq 5000$, $0\leq x\leq 10^5$) 第二行为 $n$ 个整数 $a_1, a_2,\dots,a_n$, ($-10^5\leq a_i\leq 10^5$) 所有数据的 $n$ 的总和不超过 $5000$

题目描述

You are given an array $ a_1, a_2, \dots, a_n $ , consisting of $ n $ integers. You are also given an integer value $ x $ . Let $ f(k) $ be the maximum sum of a contiguous subarray of $ a $ after applying the following operation: add $ x $ to the elements on exactly $ k $ distinct positions. An empty subarray should also be considered, it has sum $ 0 $ . Note that the subarray doesn't have to include all of the increased elements. Calculate the maximum value of $ f(k) $ for all $ k $ from $ 0 $ to $ n $ independently.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 5000 $ ) — the number of testcases. The first line of the testcase contains two integers $ n $ and $ x $ ( $ 1 \le n \le 5000 $ ; $ 0 \le x \le 10^5 $ ) — the number of elements in the array and the value to add. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -10^5 \le a_i \le 10^5 $ ). The sum of $ n $ over all testcases doesn't exceed $ 5000 $ .

输出格式

For each testcase, print $ n + 1 $ integers — the maximum value of $ f(k) $ for all $ k $ from $ 0 $ to $ n $ independently.

输入输出样例

输入样例 #1

3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4

输出样例 #1

10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8

说明

In the first testcase, it doesn't matter which elements you add $ x $ to. The subarray with the maximum sum will always be the entire array. If you increase $ k $ elements by $ x $ , $ k \cdot x $ will be added to the sum. In the second testcase: - For $ k = 0 $ , the empty subarray is the best option. - For $ k = 1 $ , it's optimal to increase the element at position $ 3 $ . The best sum becomes $ -1 + 5 = 4 $ for a subarray $ [3, 3] $ . - For $ k = 2 $ , it's optimal to increase the element at position $ 3 $ and any other element. The best sum is still $ 4 $ for a subarray $ [3, 3] $ . - For $ k = 3 $ , you have to increase all elements. The best sum becomes $ (-2 + 5) + (-7 + 5) + (-1 + 5) = 5 $ for a subarray $ [1, 3] $ .