[ARC174A] A Multiply
题面翻译
给出 N,C,A1...n。你可以选择一个区间 [l,r],让 Al,Al+1,...,Ar 全部乘上 C。至多一次操作后,求 A1...n 的和的最大值。
1≤N≤3×105, ∣C∣,∣Ai∣≤106
题目描述
長さ N の整数列 A=(A1,A2,…,AN) と整数 C が与えられます。
以下の操作を 高々 1 度 行って達成できる A の全要素の総和の最大値を求めてください。
- 1 ≤ l ≤ r ≤ N を満たす整数 l,r を指定し、 Al,Al+1,…,Ar の全ての要素を C 倍する。
输入格式
入力は以下の形式で標準入力から与えられる。
N C A1 A2 … AN
输出格式
答えを整数として出力せよ。
样例 #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
- −106 ≤ C ≤ 106
- −106 ≤ Ai ≤ 106
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 となり、これが達成可能な最大値です。