/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
長さ M の A の部分列(連続でなくてもよい) 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) は (10,20,30) の部分列ではありません。
制約
- 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
出力
答えを出力せよ。
入力例 1
4 2 5 4 -1 8
出力例 1
21
B=(A_1,A_4) とした場合、\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21 となります。22 以上の値を達成することはできないため、解は 21 です。
入力例 2
10 4 -3 1 -4 1 -5 9 -2 6 -5 3
出力例 2
54
Score : 400 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a (not necessarily contiguous) subsequence B=(B_1,B_2,\dots,B_M) of length M of A.
Notes
A subsequence of a number sequence is a sequence that is obtained by removing 0 or more elements from the original number sequence and concatenating the remaining elements without changing the order.
For example, (10,30) is a subsequence of (10,20,30), but (20,10) is not a subsequence of (10,20,30).
Constraints
- 1 \le M \le N \le 2000
- - 2 \times 10^5 \le A_i \le 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 2 5 4 -1 8
Sample Output 1
21
When B=(A_1,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21. Since it is impossible to achieve 22 or a larger value, the solution is 21.
Sample Input 2
10 4 -3 1 -4 1 -5 9 -2 6 -5 3
Sample Output 2
54