CF720F Array Covering

Misha 有一个长度为 $n$ 的整数数组。他想要选择 $k$ 个不同的连续子数组，使得数组中的每个元素至少属于其中一个被选中的子数组。 Misha 希望这样选择子数组：如果他分别计算每个子数组的元素之和，然后将所有这些子数组的和相加，结果的值要尽可能大。

输入的第一行包含两个整数：$n$，$k$（$1 \leq n \leq 100000$，$1 \leq k \leq n \cdot (n + 1)/2$） —— 数组的元素个数以及必须选择的不同子数组的数量。 第二行包含 $n$ 个整数 $a_i$（$-50000 \leq a_i \leq 50000$）—— 数组的元素。

输出一个整数 —— Misha 通过选择 $k$ 个不同子数组所能获得的最大可能值。

由 ChatGPT 5 翻译