← 返回题目列表

Codeforces · 1155/D

D. 美丽的阵列

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。数组的美妙之处在于该数组的某些连续子数组的最大和(该子数组可能为空)。例如数组[10,-5,10,-4,1]的美度为15,数组[-3,-5,-1]的美度为0。

您最多可以选择 $$$a$$$ 的一个连续子数组,并将该子数组中包含的所有值乘以 $$$x$$$。您希望在最多应用一次此类操作后最大限度地发挥数组的美感。

输入

第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 3 \cdot 10^5, -100 \le x \le 100$$$) — 分别是数组 $$$a$$$ 的长度和整数 $$$x$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$。

输出

打印一个整数 — 将属于某个连续子数组 $$$x$$$ 的所有值相乘后数组 $$$a$$$ 的最大可能美丽值。

示例

输入 #1

5 -2
-3 8 -2 1 -6

输出 #1

22

输入 #2

12 -3
1 3 3 7 1 3 3 7 1 3 3 7

输出 #2

42

输入 #3

5 10
-1 -2 -3 -4 -5

输出 #3

0

注意

在第一个测试用例中,我们需要将子数组 [-2, 1, -6] 相乘,数组变为 [-3, 8, 4, -2, 12] 与美丽 22 ([-3, 8, 4, -2, 12])。

在第二个测试用例中,我们根本不需要乘以任何子数组。

在第三个测试用例中,无论我们乘哪个子数组,数组的美丽度都将等于0。