4259: Index × A(Not Continuous ver.)

# Index × A(Not Continuous ver.) ### 内存 1024MB ### 时间 2S ## 题目描述 小高有一个长度为N的整数序列$A=(A_1,A_2,...,A_N)$。他想从中选择M个元素组成一个新的序列$B=(B_1,B_2,...,B_M)$，使得$\sum_{i=1}^{M} i \times B_i$的值最大。你帮小高计算这个最大值。 ``` B是A的一个子序列。子序列是指从原序列中删除零个或多个元素后，剩余元素保持原有顺序构成的新序列。 例如，(10,30)是(10,20,30)的一个子序列，但(20,10)不是(10,20,30)的子序列。 ``` ## 输入格式 输入从标准输入中给出，格式如下： $N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$ ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例1 ``` 4 2 5 4 -1 8 ``` ### 输出样例1 ``` 21 ``` ### 输入样例2 ``` 10 4 -3 1 -4 1 -5 9 -2 6 -5 3 ``` ### 输出样例2 ``` 54 ``` ## 数据范围与提示 【样例1说明】 当$B=(A_1,A_4)$时，我们有$\sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21$。由于不可能得到22或更大的值，所以答案是21。 【数据范围】 - $1 \le M \le N \le 2000$ - $-2 \times 10^5 \le A_i \le 2 \times 10^5$ - 所有输入均为整数。 ## 题目来源 ABC267D