[数据结构与算法]C. Increase Subarray Sums-Educational Codeforces Round 123 (Rated for Div. 2)

C. Increase Subarray Sums

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array?a1,a2,…,ana1,a2,…,an, consisting of?nn?integers. You are also given an integer value?xx.

Let?f(k)f(k)?be the maximum sum of a contiguous subarray of?aa?after applying the following operation: add?xx?to the elements on exactly?kk?distinct?positions. An empty subarray should also be considered, it has sum?00.

Note that the subarray doesn't have to include all of the increased elements.

Calculate the maximum value of?f(k)f(k)?for all?kk?from?00?to?nn?independently.

Input

The first line contains a single integer?tt?(1≤t≤50001≤t≤5000)?— the number of testcases.

The first line of the testcase contains two integers?nn?and?xx?(1≤n≤50001≤n≤5000;?0≤x≤1050≤x≤105)?— the number of elements in the array and the value to add.

The second line contains?nn?integers?a1,a2,…,ana1,a2,…,an?(?105≤ai≤105?105≤ai≤105).

The sum of?nn?over all testcases doesn't exceed?50005000.

Output

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

Example

input

Copy

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

output

Copy

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

Note

In the first testcase, it doesn't matter which elements you add?xx?to. The subarray with the maximum sum will always be the entire array. If you increase?kk?elements by?xx,?k?xk?x?will be added to the sum.

In the second testcase:

• For?k=0k=0, the empty subarray is the best option.
• For?k=1k=1, it's optimal to increase the element at position?33. The best sum becomes??1+5=4?1+5=4?for a subarray?[3,3][3,3].
• For?k=2k=2, it's optimal to increase the element at position?33?and any other element. The best sum is still?44?for a subarray?[3,3][3,3].
• For?k=3k=3, you have to increase all elements. The best sum becomes?(?2+5)+(?7+5)+(?1+5)=5(?2+5)+(?7+5)+(?1+5)=5?for a subarray?[1,3][1,3].

-----------------------------------------------------------------------------------------------------------------------------

这个题在做的时候，使用了动态规划和前缀和预处理出长度为len的各种情况，但是输出的时候发现和样例不同，当时脑子没有转过来，其实把一行代码换个位置就成了

这是本来的错误代码，看代码不难看出，我的本意是求出来固定长度再加上+k个x,求出每个长度的最值。可仔细读题会发现，题目要求的是加入k个x之后，整个数组的最大连续子段，并没有要求是必须是k长度的，放了k个最值还可能是这k个连续里面选出几段，也就是<k时的情况，所以ll ans=-0x7f7f7f7f7f那一行放置在外面就正确了，这样就可以AC了。CF的前两题是思维，第三题可能会牵扯算法，但一定不会过于繁琐，多去读题目，不要被题目绕进去

# include<iostream>
# include<algorithm>
# include<cstring>
# include<deque>
using namespace std;

typedef long long int ll;
ll dp[5050];
ll a[5050];
ll sum[5050];

int main ()
{

    int t;
    cin>>t;

    while(t--)
    {
        int n,x;
        cin>>n>>x;

       fill(dp,dp+5050,-0x7f7f7f7f);
       memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
           sum[i]=sum[i-1]+a[i];

        }

        for(int len=n;len>=0;len--)
        {
            for(int i=1;i+len-1<=n;i++)
            {
                dp[len]=max(dp[len],sum[i+len-1]-sum[i-1]);

            }
        }
         

        for(int k=0;k<=n;k++)
        {

        ll ans=-0x7f7f7f7f7f;
            for(int len=n;len>=k;len--)
            {
                ans=max(ans,dp[len]+x*k);
            }

            cout<<ans<<" ";
        }

        cout<<'\n';

    }


    return 0;
}