← 返回题目列表

Codeforces · 1580/D

D. 子序列

中文机器翻译题面 查看原题

Alice 有一个长度为 $$$n$$$ 的整数序列 $$$a$$$ 并且所有元素都不同。她将选择长度为 $$$m$$$ 的 $$$a$$$ 子序列,并将子序列 $$$a_{b_1},a_{b_2},\ldots,a_{b_m}$$$ 的值定义为 $$$$$$\sum_{i = 1}^m (m \cdot a_{b_i}) - \sum_{i = 1}^m \sum_{j = 1}^m f(\min(b_i, b_j), \max(b_i, b_j)),$$$$$$ 其中 $$$f(i, j)$$$ 表示 $$$\min(a_i, a_{i + 1}, \ldots, a_j)$$$。

Alice 希望你帮助她最大化她选择的子序列的价值。

如果 $$$s$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$t$$$ 获得,则序列 $$$s$$$ 是序列 $$$t$$$ 的子序列。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 4000$$$)。

第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i < 2^{31}$$$)。

输出

打印 Alice 可以获得的最大值。

示例

输入 #1

6 4
15 2 18 12 13 4

输出 #1

100

输入 #2

11 5
9 3 7 1 8 12 10 20 15 18 5

输出 #2

176

输入 #3

1 1
114514

输出 #3

0

输入#4

2 1
666 888

输出#4

0

注意

在第一个示例中,Alice 可以选择子序列 $$$[15, 2, 18, 13]$$$,其值为 $$$4 \cdot (15 + 2 + 18 + 13) - (15 + 2 + 2 + 2) - (2 + 2 + 2 + 2) - (2 + 2 + 18 + 12) - (2 + 2 + 12 + 13) = 100$$$。在第二个示例中,有多种值为 $$$176$$$ 的子序列,其中之一是 $$$[9, 7, 12, 20, 18]$$$。