You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC174A] A Multiply

题目描述

给出 $N,C,A_{1...n}$。你可以选择一个区间 $[l,r]$，让 $A_l,A_{l+1},...,A_r$ 全部乘上 $C$。至多一次操作后，求 $A_{1...n}$ 的和的最大值。当然，你可以不操作。

$1\le N\le 3\times 10^5,\space \space |C|,|A_i|\le 10^6$

输入格式

第一行两个整数 $N,C$ ，第二行 $N$ 个整数 $A_i$ 。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

5 2
-10 10 20 30 -20

样例输出 #1

90

样例 #2

样例输入 #2

5 1000000
-1 -2 -3 -4 -5

样例输出 #2

-15

样例 #3

样例输入 #3

9 -1
-9 9 -8 2 -4 4 -3 5 -3

样例输出 #3

13

数据范围

对 $100\%$ 的数据，$1\ \le\ N\ \le\ 3\ \times\ 10^5$，$-10^6\ \le\ C\ \le\ 10^6$，$-10^6\ \le\ A_i\ \le\ 10^6$

样例解释 1

$A=(-10,10,20,30,-20),\ C=2$ ，指定 $l=2,r=4$ ，则操作后 $A$ 变成 $(-10,20,40,60,-20)$ ， $A$ 中元素总和是 $90$ ，是可能的最大值。

样例解释 2

$A=(-1,-2,-3,-4,-5),\ C=1000000$ ， 不操作即可。