102672: [AtCoder]ABC267 C - Index × A(Continuous ver.)

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Find the maximum value of $\displaystyle \sum_{i=1}^{M} i \times B_i$ for a contiguous subarray $B=(B_1,B_2,\dots,B_M)$ of $A$ of length $M$.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing $0$ or more initial terms and $0$ or more final terms from the original number sequence.

For example, $(2, 3)$ and $(1, 2, 3)$ are contiguous subarrays of $(1, 2, 3, 4)$, but $(1, 3)$ and $(3,2,1)$ are not contiguous subarrays of $(1, 2, 3, 4)$.

Constraints

• $1 \le M \le N \le 2 \times 10^5$
• $- 2 \times 10^5 \le A_i \le 2 \times 10^5$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

15

When $B=(A_3,A_4)$, we have $\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15$. Since it is impossible to achieve $16$ or a larger value, the solution is $15$.

Note that you are not allowed to choose, for instance, $B=(A_1,A_4)$.

Sample Input 2

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

Sample Output 2

31

问题描述

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

找到 A 的长度为 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$

输出

输出答案。

样例输入 1

4 2
5 4 -1 8

样例输出 1

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)$。

样例输入 2

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

样例输出 2

31