#10991. A Multiply Multiply ARC比赛编号174

A Multiply Multiply ARC比赛编号174

[ARC174A] A Multiply

题面翻译

给出 N,C,A1...nN,C,A_{1...n}。你可以选择一个区间 [l,r][l,r],让 Al,Al+1,...,ArA_l,A_{l+1},...,A_r 全部乘上 CC。至多一次操作后,求 A1...nA_{1...n} 的和的最大值。

1N3×105,  C,Ai1061\le N\le 3\times 10^5,\space \space |C|,|A_i|\le 10^6

题目描述

長さ N N の整数列 A=(A1,A2,,AN) A=(A_1,A_2,\dots,A_N) と整数 C C が与えられます。 以下の操作を 高々 1 1 行って達成できる A A の全要素の総和の最大値を求めてください。

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

输入格式

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

N N C C A1 A_1 A2 A_2 \dots AN 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  N  3 × 105 1\ \le\ N\ \le\ 3\ \times\ 10^5
  • 106  C  106 -10^6\ \le\ C\ \le\ 10^6
  • 106  Ai  106 -10^6\ \le\ A_i\ \le\ 10^6

Sample Explanation 1

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

Sample Explanation 2

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