UOJ Logo Zijian Online Judge

ZOJ

#40. 排序

Statistics

众所周知,fpdqwq同学会很多算法,尤其擅长排序。但这题不仅和排序没有任何关系,甚至和fpdqwq也没有关系。

这次我们的主人公是小明同学。一天,小明打算去买酒喝,他家里有$n$个瓶子,然而瓶子太多了,他只打算带$k$个瓶子去集市上。

小明将$k$个瓶子交给商人之后,商人用它们装一些酒给小明。所有的瓶子都没有刻度,只在瓶口标注了容量,第$i$个瓶子的容量为$V_i$。商人比较吝啬,他们并不会把所有的瓶子都装满酒。他们拿到瓶子后,会跑到酒桶附近鼓捣一通,弄出一小点酒来交差。小明当然知道他们会来这一手,于是事先了解了商人鼓捣的具体内容。

商人在酒桶边只会做如下的3种操作:

1.将某个瓶子装满酒;

2.将某个瓶子中的酒全部倒回酒桶;

3.将酒从瓶子$a$倒向瓶子$b$,直到瓶子$b$满或者瓶子$a$空。倾倒过程中的损耗可以忽略。

商人拿出的酒,当然是这些操作能得到的最小正体积。小明知道,对于不同的瓶子组合,商人可能会被迫给出不同体积的酒。小明希望找到最优的瓶子组合,使得商人给出尽量多的酒。

由于小明想在携带的瓶子个数和获得的酒量之间做权衡(???),所以请对所有的$k$($1\leq k \leq n$)输出答案

输入格式

第一行两个整数$n,maxv$,表示瓶子个数和瓶子最大容量

接下来一行$n$个整数,用空格分隔,分别表示每个瓶子的容量$V_i$

输出格式

一行$n$个整数,用空格分隔,第$i$个数代表$k=i$时的答案

样例一

input

3 4
3 4 4

output

4 4 1 

样例解释

$k=1$时,只需要随便取一个最大的瓶子,商人无论怎么捣腾都无法给小明小于4体积的酒。

$k=2$时,只需要取两个最大的瓶子,商人无论怎么捣腾都无法给小明小于4体积的酒。

$k=3$时,必须把所有瓶子都带上。

商人可以对容量为4的瓶子执行操作1,再对这个瓶子和容量为3的瓶子执行操作3,再对容量为3的瓶子执行操作2,即可获得1体积的酒。

样例二

input

1 1000000
1000000

output

1000000 

样例解释

$k=1$时,商人无论怎么捣腾都无法给小明小于1000000体积的酒。

数据范围与约定

子任务1 (13 pts): $1\leq n \leq 10$

子任务2 (34 pts): $1\leq n \leq 5000$

子任务3 (53 pts): 无额外限制

对于全部数据:$1 \leq n,maxv \leq 1000000$,$1 \leq V_i \leq maxv$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

提示

1.读入量较大,请注意读入效率

2.佛曰:皤佛佛怯曳罰是冥伽豆梵瑟呐參顛呐摩呐無怯羅訶隸提菩