CF1796D.Maximum Subarray
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a1,a2,…,an , consisting of n integers. You are also given two integers k and x .
You have to perform the following operation exactly once: add x to the elements on exactly k distinct positions, and subtract x from all the others.
For example, if a=[2,−1,2,3] , k=1 , x=2 , and we have picked the first element, then after the operation the array a=[4,−3,0,1] .
Let f(a) be the maximum possible sum of a subarray of a . The subarray of a is a contiguous part of the array a , i. e. the array ai,ai+1,…,aj for some 1≤i≤j≤n . An empty subarray should also be considered, it has sum 0 .
Let the array a′ be the array a after applying the aforementioned operation. Apply the operation in such a way that f(a′) is the maximum possible, and print the maximum possible value of f(a′) .
输入格式
The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases.
The first line of each test case contains three integers n , k and x ( 1≤n≤2⋅105 ; 0≤k≤min(20,n) ; −109≤x≤109 ).
The second line contains n integers a1,a2,…,an ( −109≤ai≤109 ).
The sum of n over all test cases doesn't exceed 2⋅105 .
输出格式
For each test case, print one integer — the maximum possible value of f(a′) .
输入输出样例
输入#1
4 4 1 2 2 -1 2 3 2 2 3 -1 2 3 0 5 3 2 4 6 2 -8 4 -1 9 -3 7 -8
输出#1
5 7 0 44