← 返回题目列表

AtCoder · KeioPC2025_b

B. 累积和最小化

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

配点 : 100 点

問題文

长度 小于或等于 N 的非负整数序列 A = (A_1, A_2, ..., A_N) 。 你可以执行以下操作 执行次数不得超过 0 回以上 K 次。

  • 1 \leq i \leq N 的整数 选择 i ,A_i 该值应乘以 0 。

长度 小于或等于 N 整数序列 给出 B = (B_1, B_2, ..., B_N) , \displaystyle B_i = \sum_{j=1}^{i} A_j 中定义。决赛 求 \displaystyle\sum_{i=1}^{N} B_i 的最小可能值。

制約

  • 1 \leq K \leq N \leq 3 \times 10^5
  • 0 \leq A_i \leq 10^7
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N\ K
A_1\ A_2\ ...\ A_N

出力

打印答案。 来自


入力例 1

5 2
1 1 3 2 9

出力例 1

13

i = 3, 5 运行时 A = (1, 1, 0, 2, 0) , B = (1, 2, 2, 4, 4) 变为 通过B 的总和为 13 。
无论你如何操作 B 的总和 12 不能小于或等于,所以答案是 13 。 对于


入力例 2

4 1
6 0 2 6

出力例 2

10

入力例 3

3 3
2 3 8

出力例 3

0