求大赏关

//思路：找出目前价值最大的字段，多退少补给所有字段的数+/-k，暴力 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=2e5+5;
inline int read()
{
	int f=1,k=0;
	char c=getchar();//读入一个字符 
	//非数字 
	while(c<'0'||c>'9')//读到空格后
	{
		if(c=='-')f=-1;//读到负数  
		c=getchar();//两个功能：读取负号后面的数字或者读入空格等。 
	}
	//数字 
	while(c>='0'&&c<='9')
	{
		k=(k<<1)+(k<<3)+(c^48);
		c=getchar();//一位一位读入数字 
	}
	return f*k;	
}
int t; 
signed main()
{
	t=read();
	while(t--)
	{
		int n=read(),k=read(),x=read(),a[M],sum[M]={0},ma[M]={0},ans=-1;
		for(register int i=1;i<=n;i++)
		{
			a[i]=read();sum[i]=sum[i-1]+a[i];
		}
		for(register int i=1;i<=n;i++)//枚举长度
		{
			for(register int j=1;j<=n-i+1;j++)ma[i]=max(sum[i+j-1]-sum[i-1],ma[i]);
			//枚举起点
			int res;
			if(x>=0)res=ma[i]+k*x-(i-k)*x;
			else res=ma[i]+min(n-k,i)*(-x)+(i-min(n-k,i))*x;
			ans=max(ans,res);
		}
		cout<<ans<<endl;
	}
	return 0;
}