1336 - 开心吃巧克力
时间限制 : 1 秒
内存限制 : 128 MB
Bessie 拿到了 N(1 \leq N \leq 5\times 10 ^ 4)块巧克力。她决定想个办法吃掉这些巧克力,使得它在吃巧克力的这段时间里,最不开心的一天尽可能的开心。并且一共吃 D(1 \leq D \leq 5\times 10 ^ 4)天。
每块巧克力有一个开心值 H_i(1 \leq H_i \leq 10 ^ 6),当某天你吃下那块巧克力时,你将获得那块巧克力的开心值。每一天的开心值是所有当天吃掉的巧克力的总开心值之和。每天晚上 Bessie 睡觉之后,它的开心值会减半。也就是说,比如昨天 Bessie 的开心值为 50,那么今天早上一醒来就会有 25 点的开心值,舍去小数点后数字。另外,Bessie 还有一个怪癖,她喜欢按照巧克力本来的排列顺序吃。
Bessie 第一天的开心值为 0,求一个每天吃巧克力的方案,使得 Bessie 最不开心的一天尽可能的开心。
输入
第一行:两个整数 N 和 D,中间用空格分隔。
第 2 行至第 N + 1 行:每行一个整数,第 i + 1 行表示 H_i 的值。
输出
第一行:一个整数,表示 Bessie 在 D 天中最不开心的一天最大可能的开心值。
第 2 至第 n + 1 行,每行一个整数,第 i + 1 行表示 Bessie 吃第 i 块巧克力的日期。
样例
输入
5 5 10 40 13 22 7
输出
24 1 1 3 4 5
来源
USACO