[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$ の整数列 $A=(A_1,A_2,\dots,A_N)$ と整数 $C$ が与えられます。 以下の操作を 高々 $1$ 度 行って達成できる $A$ の全要素の総和の最大値を求めてください。

• $1\ \le\ l\ \le\ r\ \le\ N$ を満たす整数 $l,r$ を指定し、 $A_l,A_{l+1},\dots,A_r$ の全ての要素を $C$ 倍する。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $C$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

答えを整数として出力せよ。

样例 #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

提示

制約

• 入力は全て整数
• $1\ \le\ N\ \le\ 3\ \times\ 10^5$
• $-10^6\ \le\ C\ \le\ 10^6$
• $-10^6\ \le\ A_i\ \le\ 10^6$

Sample Explanation 1

この入力では、 $A=(-10,10,20,30,-20),\ C=2$ です。 $l=2,r=4$ と指定して操作を $1$ 度行うことで、操作後の $A$ を $(-10,20,40,60,-20)$ とすることができます。 このとき $A$ の全要素の総和は $90$ となり、これが達成可能な最大値です。

Sample Explanation 2

この入力では、 $A=(-1,-2,-3,-4,-5),\ C=1000000$ です。 操作を一度も行わないとき $A$ の全要素の総和は $-15$ となり、これが達成可能な最大値です。