分数: 466 分
问题陈述
Takahashi 有一个整数序列 A_1, A_2, \ldots, A_N 长度 N.
Takahashi 想要选择一个连续的区间 W 此序列中的元素并最大化其 评价分数.
具体来说,他选择一个整数 l (1 \leq l \leq N - W + 1) 并定义区间的评估分数 A_l, A_{l+1}, \ldots, A_{l+W-1} 由以下公式计算:
\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})
即评价分数为区间内元素之和加上区间内最小值与整数的乘积 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
- 第一行包含整数 N 表示序列的长度,整数 W 表示区间长度,整数 K 表示系数乘以最小值,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 表示序列的元素,以空格分隔。
输出
在单行上以整数形式输出最大评估分数。
示例输入 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