Index × A(Continuous ver.)

题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。 对于长度为 $M$ 的 $A$ 的一个连续子数组 $B=(B_1,B_2,\dots,B_M)$，求 $\displaystyle \sum_{i=1}^{M} i \times B_i$ 的最大值。

输入格式

输入采用标准输入，格式如下： $N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

4 2
5 4 -1 8

15

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

31

提示

$1 \le M \le N \le 2 \times 10^5$ $- 2 \times 10^5 \le A_i \le 2 \times 10^5$ 输入中的所有数值均为整数。序列的 连续子数组 是指通过从原序列中去掉 $0$ 个或多个前导项和 $0$ 个或多个末尾项得到的序列。例如，$(2, 3)$ 和 $(1, 2, 3)$ 是 $(1, 2, 3, 4)$ 的连续子数组，但 $(1, 3)$ 和 $(3,2,1)$ 不是 $(1, 2, 3, 4)$ 的连续子数组。当 $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)$。

标签: AtCoder|abc267C

来源

AtCoder|abc267C