← 返回题目列表

Codeforces · 1253/C

C. 吃甜食

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

紬给轻音乐社带来了$$$n$$$美味的糖果。它们的编号从 $$$1$$$ 到 $$$n$$$,其中第 $$$i$$$ 个糖果的糖浓度由整数 $$$a_i$$$ 描述。

Yui喜欢甜食,但出于健康原因,她每天最多只能吃$$$m$$$甜食。

天按 $$$1$$$ 索引(编号为 $$$1, 2, 3, \ldots$$$)。在第 $$$d$$$ 天吃甜食 $$$i$$$ 会导致糖分损失 $$$(d \cdot a_i)$$$,因为随着时间的推移,甜食变得越来越含糖。一颗甜食最多可以吃一次。

总糖罚分将是所吃的每种甜食的单独罚分之和。

假设 Yui 恰好选择了 $$$k$$$ 糖果,并按照她想要的任何顺序吃掉它们。她能得到的最低总糖罚分是多少?

由于 Yui 是一个犹豫不决的女孩,她希望您针对 $$$1$$$ 和 $$$n$$$ 之间的每个 $$$k$$$ 值回答这个问题。

输入

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

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 200\ 000$$$)。

输出

你必须在一行中输出 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$,并用空格分隔,其中 $$$x_k$$$ 是 Yui 吃了 $$$k$$$ 糖果后可以获得的最小总糖罚分。

示例

输入 #1

9 2
6 19 3 4 4 2 6 7 8

输出 #1

2 5 11 18 30 43 62 83 121

输入 #2

1 1
7

输出 #2

7

注意

我们来分析第一个例子中 $$$k = 5$$$ 的答案。以下是吃 $$$5$$$ 糖果的可能方法之一,可以最大限度地减少总糖分损失:

- 天 $$$1$$$:糖果 $$$1$$$ 和 $$$4$$$
- 天 $$$2$$$:糖果 $$$5$$$ 和 $$$3$$$
- 天 $$$3$$$ : 甜 $$$6$$$

总罚款为 $$$1 \cdot a_1 + 1 \cdot a_4 + 2 \cdot a_5 + 2 \cdot a_3 + 3 \cdot a_6 = 6 + 4 + 8 + 6 + 6 = 30$$$。我们可以证明,如果 Yui 吃 $$$5$$$ 糖果,这是她可以达到的最小总糖罚分,因此 $$$x_5 = 30$$$。