102673: [AtCoder]ABC267 D - Index × A(Not Continuous ver.)
Description
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
Input
题意翻译
### 题目描述 有一个长度为 $N$ 整数数列 $A=(A_1,A_2,...,A_N)$ 。 现在假设有一个长度为 $M$ 的序列 $B$ ,并且 $B$ 是 $A$ 的**子序列**。请找到 $\sum_{i=1}^M i\times B_i$ 的最大值。 ### 输入格式 输入按照下面的标准格式给出： > $ N\ M \newline A_1 \ A_2 \ \dots\ A_N $ ### 输出格式 一个整数，表示$\sum_{i=1}^M i\times B_i$ 的最大值。 ### 说明 / 提示 #### 注意事项 若序列 $S$ 是长度为 $L$ 的数列 $T$ 的**子序列**，则 $S$ 是数列 $T$ 删除任意 $i\ (i\in [0,L])$ 个元素得到的。 比如说， $(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$ + 所有输入数据均为整数 #### 样例解释 对于**样例一**，当 $B=(A_1,A_4)$ 时，$\sum_{i=1}^M i\times B_i=1\times 5+2\times 8=21$ 。因为不可能达到 $22$ 或者更大的值，所以答案是 $21$ 。Output
分数：400分
问题描述
给你一个长度为 $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$ 的值最大。
注释
一个数列的 子序列 是从原始数列中删除 $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