/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ 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 倍する。
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- -10^6 \le C \le 10^6
- -10^6 \le A_i \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
N C A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
5 2 -10 10 20 30 -20
出力例 1
90
この入力では、 A=(-10,10,20,30,-20), C=2 です。
l=2,r=4 と指定して操作を 1 度行うことで、操作後の A を (-10,20,40,60,-20) とすることができます。
このとき A の全要素の総和は 90 となり、これが達成可能な最大値です。
入力例 2
5 1000000 -1 -2 -3 -4 -5
出力例 2
-15
この入力では、 A=(-1,-2,-3,-4,-5), C=1000000 です。
操作を一度も行わないとき A の全要素の総和は -15 となり、これが達成可能な最大値です。
入力例 3
9 -1 -9 9 -8 2 -4 4 -3 5 -3
出力例 3
13
Score: 300 points
Problem Statement
You are given an integer sequence of length N, A=(A_1,A_2,\dots,A_N), and an integer C.
Find the maximum possible sum of the elements in A after performing the following operation at most once:
- Specify integers l and r such that 1 \le l \le r \le N, and multiply each of A_l,A_{l+1},\dots,A_r by C.
Constraints
- All input values are integers.
- 1 \le N \le 3 \times 10^5
- -10^6 \le C \le 10^6
- -10^6 \le A_i \le 10^6
Input
The input is given from Standard Input in the following format:
N C A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
5 2 -10 10 20 30 -20
Sample Output 1
90
In this input, A=(-10,10,20,30,-20), C=2.
After performing the operation once specifying l=2 and r=4, A will be (-10,20,40,60,-20).
Here, the sum of the elements in A is 90, which is the maximum value achievable.
Sample Input 2
5 1000000 -1 -2 -3 -4 -5
Sample Output 2
-15
In this input, A=(-1,-2,-3,-4,-5), C=1000000.
Without performing the operation, the sum of the elements in A is -15, which is the maximum value achievable.
Sample Input 3
9 -1 -9 9 -8 2 -4 4 -3 5 -3
Sample Output 3
13