#CW22. 切割(cut)

切割(cut)

题目描述

有 nn 根木棍,第 ii 根木棍的长度为 aia_i。

你可以使用一种切割机器。每次操作时,选择若干根木棍,并指定一个正整数 xx。对于每根被选中的、长度为 ll 的木棍:

  • 若 l≤xl \le x,则木棍保持不变;
  • 若 l>xl>x,则将其切成两根长度分别为 xx 和 l−xl-x 的木棍。

切割后得到的木棍仍然可以继续被切割。

对于每个 k=1,2,…,mk=1,2,\ldots,m,独立考虑恰好进行 kk 次操作的情况,求最终最多能得到多少根长度完全相同的木棍。

注意,你只需要让某一种长度相同的木棍尽量多,对于该种数量最多的木棍的长度并没有要求。

即,设最后切割成了 hh 根木棍,长度分别是 p1,p2,…,php_1,p_2,\ldots,p_h,你要最大化

max⁡s∑i=1h[pi=s].\max_s \sum_{i=1}^{h} [p_i=s].

例如,切割后的长度为 [1,1,2,2,2,3,3,4][1,1,2,2,2,3,3,4],答案为 33,因为有 33 根长度为 22 的木棍。

输入格式

第一行包含两个整数 n,mn,m。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一行 mm 个整数,表示 k=1,2,…,mk=1,2,\ldots,m 时的答案。

样例 1 输入

5 4
1 2 3 4 4

样例 1 输出

6 14 14 14

样例 1 解释

当 k=1k=1,选择 x=2x=2 切割 [2,3,4,4][2,3,4,4],变成 [1,2,2,1,2,2,2,2][1,2,2,1,2,2,2,2]。

当 k=2k=2,第一次选择 x=2x=2 切割 [2,3,4,4][2,3,4,4],变成 [1,2,2,1,2,2,2,2][1,2,2,1,2,2,2,2];第二次选择 x=1x=1 切割所有长度为 22 的木棍。

样例 2 输入

7 9
1 7 5 1 7 5 3

样例 2 输出

7 17 29 29 29 29 29 29 29

数据范围

对于所有测试数据,保证:1≤n,m≤2×1051 \le n,m \le 2 \times 10^5,1≤ai≤m1 \le a_i \le m。

测试点 n≤n \le m≤m \le 特殊性质
1∼51 \sim 5 77 无
6∼86 \sim 8 100100
9∼129 \sim 12 10001000
13∼1513 \sim 15 2×1052 \times 10^5 ∀i\forall i,存在 kk 使得 ai=2ka_i=2^k
16∼2016 \sim 20 无