当前没有测试数据。

C - Index × A（连续版）

得分：$300$ 分。

问题描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。

找到长度为 $M$ 的连续子数组 $B=(B_1,B_2,\dots,B_M)$ 使得 $\displaystyle \sum_{i=1}^{M} i \times B_i$ 的值最大。

注意事项

一个序列的连续子数组是指从原始序列中删除 $0$ 个或多个开始的项和 $0$ 个或多个结尾的项所得到的序列。

例如，$(2, 3)$ 和 $(1, 2, 3)$ 是序列 $(1, 2, 3, 4)$ 的连续子数组，但是$(1, 3)$ 和 $(3,2,1)$ 不是序列$(1, 2, 3, 4)$ 的连续子数组。

约束条件

• $1 \le M \le N \le 2 \times 10^5$
• $-2 \times 10^5 \le A_i \le 2 \times 10^5$
• 所有输入值都是整数。

输入

输入以以下格式给出：

$N$ $M$

$A_1$ $A_2$ $\dots$ $A_N$

输出

输出答案。

4 2
5 4 -1 8

15

当 $B=(A_3,A_4)$ 时，我们有 $\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15$。因为不可能得到 $16$ 或一个更大的值，所以答案是 $15$。

注意，你不能选择 $B=(A_1,A_4)$。

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

31