← 返回题目列表

AtCoder · awc0045_e

E. 区间评价值

中文机器翻译题面 查看原题

分数: 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