/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
高橋君は長さ N の整数列 A_1, A_2, \ldots, A_N を持っています。
高橋君は、この数列から連続する W 個の要素からなる区間を 1 つ選び、その 評価値 を最大化したいと考えています。
具体的には、整数 l （ 1 \leq l \leq N - W + 1 ）を 1 つ選び、区間 A_l, A_{l+1}, \ldots, A_{l+W-1} の評価値を次の式で定義します：
\text{評価値} = \left(\sum_{i=l}^{l+W-1} A_i\right) + K \times \min(A_l, A_{l+1}, \ldots, A_{l+W-1})
すなわち、評価値は区間内の要素の総和に、区間内の最小値と整数 K の積を加えたものです。
K および各 A_i は正・零・負のいずれの値もとりえることに注意してください。
l としてありうるすべての値（ 1 \leq l \leq N - W + 1 ）に対する評価値の最大値を求めてください。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq W \leq N
- -10^6 \leq K \leq 10^6
- -10^9 \leq A_i \leq 10^9 （ 1 \leq i \leq N ）
- 入力はすべて整数である
入力
N W K A_1 A_2 \ldots A_N
- 1 行目には、数列の長さを表す整数 N、区間の長さを表す整数 W、最小値に掛ける係数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、数列の各要素を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
評価値の最大値を整数として 1 行で出力せよ。
入力例 1
5 3 2 1 3 2 5 4
出力例 1
15
入力例 2
4 2 -3 5 1 4 3
出力例 2
3
入力例 3
10 4 5 -3 7 -2 8 1 -5 6 3 -1 4
出力例 3
7
入力例 4
20 5 -2 10 -7 3 8 -1 6 2 -4 9 5 -3 7 1 -8 4 11 -6 2 0 3
出力例 4
31
入力例 5
1 1 1000000 -1000000000
出力例 5
-1000001000000000
Score : 466 pts
Problem Statement
Takahashi has an integer sequence A_1, A_2, \ldots, A_N of length N.
Takahashi wants to select one contiguous interval of W elements from this sequence and maximize its evaluation score.
Specifically, he chooses an integer l (1 \leq l \leq N - W + 1) and defines the evaluation score of the interval A_l, A_{l+1}, \ldots, A_{l+W-1} by the following formula:
\text{Evaluation Score} = \left(\sum_{i=l}^{l+W-1} A_i\right) + K \times \min(A_l, A_{l+1}, \ldots, A_{l+W-1})
That is, the evaluation score is the sum of the elements in the interval plus the product of the minimum value in the interval and the integer K.
Note that K and each A_i can be positive, zero, or negative.
Find the maximum evaluation score over all possible values of l (1 \leq l \leq N - W + 1).
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq W \leq N
- -10^6 \leq K \leq 10^6
- -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N W K A_1 A_2 \ldots A_N
- The first line contains the integer N representing the length of the sequence, the integer W representing the length of the interval, and the integer K representing the coefficient multiplied by the minimum value, separated by spaces.
- The second line contains the integers A_1, A_2, \ldots, A_N representing the elements of the sequence, separated by spaces.
Output
Output the maximum evaluation score as an integer on a single line.
Sample Input 1
5 3 2 1 3 2 5 4
Sample Output 1
15
Sample Input 2
4 2 -3 5 1 4 3
Sample Output 2
3
Sample Input 3
10 4 5 -3 7 -2 8 1 -5 6 3 -1 4
Sample Output 3
7
Sample Input 4
20 5 -2 10 -7 3 8 -1 6 2 -4 9 5 -3 7 1 -8 4 11 -6 2 0 3
Sample Output 4
31
Sample Input 5
1 1 1000000 -1000000000
Sample Output 5
-1000001000000000