4129: 非连续子数组的最大值
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
# Index × A(Continuous ver.)
## 题目描述
给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,...,A_N)$。找出 $A$ 的一个长度为 $M$ 的连续子数组 $B=(B_1,B_2,...,B_M)$，使得 $\sum_{i=1}^{M} i \times B_i$ 的值最大。请计算并输出这个最大值。
连续子数组是指从原序列中删除 0 个或多个开头元素和 0 个或多个结尾元素后得到的序列。
例如，(2, 3) 和 (1, 2, 3) 是 (1, 2, 3, 4) 的连续子数组，但 (1, 3) 和 (3, 2, 1) 不是。
输入
## 输入格式
输入从标准输入中给出，格式如下：
$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$
输出
## 输出格式
输出所求答案。
样例输入 复制
4 2
5 4 -1 8样例输出 复制
15提示
## 输入输出样例
### 输入样例1
```
4 2
5 4 -1 8
```
### 输出样例1
```
15
```
### 输入样例2
```
10 4
-3 1 -4 1 -5 9 -2 6 -5 3
```
### 输出样例2
```
31
```
## 数据范围与提示
【样例1说明】
当 $B=(A_3,A_4)$ 时，我们有 $\sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15$。由于不可能得到 16 或更大的值，所以答案是 15。
注意，你不能选择例如 $B=(A_1,A_4)$。
【数据范围】
- $1 \le M \le N \le 2 \times 10^5$
- $-2 \times 10^5 \le A_i \le 2 \times 10^5$
- 所有输入均为整数。
## 题目来源
ABC267C