Orange的滑动窗口

题目描述

滑动窗口，又叫做尺取法，是双指针算法的一种典型模型。在各大竞赛中频繁出现，Orange相信你已经熟练掌握了这种算法！Ciallo～(∠・ω< )⌒★

Orange定义一个"窗口"为序列的一个长度为 $k$ 连续子序列，并且定义一个窗口 $a_L a_{L+1} \cdots a_{L+k-1}$ 的权值为窗口中第 $i$ 个数与 $i$ 的乘积之和，形式化的公式如下:

你的任务是，求出权值最大的窗口的权值。

输入格式

输入包含2行，第一行为2个整数 $n$ 和 $k$，表示序列长度和窗口长度。 第二行为 $n$ 个整数 $a_i$，表示序列的元素。

数据范围:

对于 $20\%$ 的数据， $n \le 2000$。 对于所有数据， $n \le 2 \times 10^5, 1 \le k \le n$, $|a_i| \le 10^5$。

输出格式

输入一个整数，表示答案。

样例 #1

样例输入 #1

5 3
1 -2 3 -1 5

样例输出 #1

16

提示

窗口 $[a_3,a_4,a_5]$ 的权值为 $1 \times 3 + 2 \times (-1) + 3 \times 5 = 16$，可以证明这是权值最大的窗口。