CF940E Cashback

由于你是最强的 Wraith King，位于文尼察市中心的 Nizhniy Magazin «Mir» 正在为你提供折扣。 给定一个长度为 $n$ 的数组 $a$ 和一个整数 $c$。 对于长度为 $k$ 的某个数组 $b$，其“价值”定义为其所有元素之和，减去其中最小的 $\lfloor \frac kc \rfloor$ 个元素。例如，数组 $[3,1,6,5,2]$ 在 $c=2$ 时的价值为 $3+6+5=14$。 请在所有可能将 $a$ 划分为若干个连续子数组的方案中，输出这些子数组的价值之和的最小值。

第一行包含两个整数 $n$ 和 $c$（$1 \leq n, c \leq 100000$）。 第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。

输出一个整数，表示某种划分下所有子数组的价值之和的最小值。

在第一个样例中，任何一种划分方式的总价值都是 6。 在第二个样例中，一种最优划分方式为 $[1,1],[10,10,10,10,10,10,9,10,10,10]$，其价值分别为 2 和 90。 在第三个样例中，一种最优划分方式为 $[2,3],[6,4,5,7],[1]$，其价值分别为 3、13 和 1。 在第四个样例中，一种最优划分方式为 $[1],[3,4,5,5,3,4],[1]$，其价值分别为 1、21 和 1。 由 ChatGPT 4.1 翻译