Index × A(Not Continuous ver.)

题目描述

你得到一个长度为 $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$ 最大的值。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

4 2
5 4 -1 8

21

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

54

提示

$1 \le M \le N \le 2000$ $- 2 \times 10^5 \le A_i \le 2 \times 10^5$ 输入中的所有值都是整数。一个数列的 子序列 是通过从原始数列中删除 $0$ 个或多个元素并按原顺序连接剩余元素得到的序列。 例如，$(10,30)$ 是 $(10,20,30)$ 的一个子序列，但 $(20,10)$ 不是 $(10,20,30)$ 的子序列。当 $B=(A_1,A_4)$ 时，我们有 $\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21$。 由于不可能达到 $22$ 或更大的值，答案是 $21$。

标签: AtCoder|abc267D

来源

AtCoder|abc267D