← 返回题目列表

Codeforces · 1175/G

G. 又一个分区问题

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

给定数组 $$$a_1, a_2, \dots, a_n$$$。您需要将其拆分为 $$$k$$$ 子段(因此每个元素都包含在一个子段中)。

子分段 $$$a_l, a_{l+1}, \dots, a_r$$$ 的权重等于 $$$(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$$$。分区的权重是其所有分段的总权重。

找到权重最小的分区。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^4$$$, $$$1 \le k \le \min(100, n)$$$) — 数组 $$$a$$$ 的长度和分区中子段的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^4$$$) — 数组 $$$a$$$。

输出

打印单个整数 — 所有可能分区中的最小权重。

示例

输入 #1

4 2
6 1 7 4

输出 #1

25

输入 #2

4 3
6 1 7 4

输出 #2

21

输入 #3

5 4
5 1 5 1 5

输出 #3

21

注意

第一个示例中的最佳分区如下:$$$6$$$ $$$1$$$ $$$7$$$ $$$\bigg|$$$ $$$4$$$。

第二个示例中的最佳分区如下:$$$6$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$7$$$ $$$4$$$。

第三个示例中的最佳分区之一如下:$$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$5$$$。