当前没有测试数据。

D - 索引乘以 A（非连续版本）

得分：$400$ 分

问题描述

给定一个长度为 $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$ 个或多个元素，并连接剩余的元素而得到的序列，但不改变顺序。

例如，$(10,30)$ 是 $(10,20,30)$ 的子序列，但 $(20,10)$ 不是。

约束

• $1 \le M \le N \le 2000$
• $-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

21

当$B=(A_1,A_4)$时，我们有 $\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21$。由于无法得到$22$或更大的值，答案是$21$。

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

54