#P17954. Exchange Error
Exchange Error
Exchange Error
题目描述
给定长度为 的整数数组 。对于一个整数 ,把数组的每个元素都加上 ,并定义
$$S(x)=\max_{1\le l\le r\le n}\sum_{i=l}^{r}(a_i+x).$$给定 个 ,分别求出 。每个询问都使用原数组 ,平移量不会在询问之间累积。
所选子数组必须非空,因此答案可能为负数。
输入格式
第一行一个整数 ,表示测试用例数,。
每组测试用例包含三行:
- 第一行两个整数 ,。
- 第二行 个整数 ,。
- 第三行 个整数,依次为各询问的平移量 ,。
所有测试用例的 之和不超过 , 之和也不超过 。
输出格式
每组测试用例输出一行 个整数,按询问的输入顺序给出答案。
样例 1
输入
2
5 7
1 2 6 9 -4
0 -1 -20 -2 5 -4 -8
7 8
6 -14 1 5 -14 3 -8
-5 -3 0 4 5 6 8 9
输出
18 14 -11 11 39 7 1
1 3 6 14 18 23 35 42