You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Bessie 从公牛们那里收到了 $N$（$1 \leq N \leq 5\times10^4$）块巧克力，但她不想吃得太快，所以她计划在接下来的 $D$（$1 \leq D \leq 5\times10^4$）天内安排吃巧克力的日程，以使这些天中她每天的最低幸福值尽可能高。

Bessie 的幸福值是一个整数，初始为 $0$，每晚睡觉时会减半（如果有小数则向下取整）。然而，当她吃掉第 $i$ 块巧克力时，幸福值会增加整数 $H_i$（$1 \leq H_i \leq 1\times10^6$）。如果她在某天吃巧克力，那么当天的幸福值以吃完巧克力后的值为准。Bessie 坚持要按照收到巧克力的顺序来吃。

如果有多个最优解，输出任意一个即可。

考虑一个要在 $5$ 天内吃完 $5$ 块巧克力的例子，它们分别带来的幸福值为 $(10, 40, 13, 22, 7)$。

如果 Bessie 在第一天吃掉第一块巧克力（$10$ 幸福值），然后等待之后再吃其他巧克力，她第一天的幸福值就是 $10$。

以下是一个最大化最低幸福值的完整安排：

第 $1$ 天：起床时幸福值 $0$ → 吃掉 $10+40$ → 睡前幸福值 $50$。

第 $2$ 天：起床时幸福值 $25$ → 不吃 → 睡前幸福值 $25$。

第 $3$ 天：起床时幸福值 $12$ → 吃掉 $13$ → 睡前幸福值 $25$。

第 $4$ 天：起床时幸福值 $12$ → 吃掉 $22$ → 睡前幸福值 $34$。

第 $5$ 天：起床时幸福值 $17$ → 吃掉 $7$ → 睡前幸福值 $24$。

这样得到的最低睡前幸福值是 $24$，这是 Bessie 能做到的最好结果。

输入格式

• 第 $1$ 行：两个用空格分隔的整数：$N$ 和 $D$。
• 第 $2\sim N+1$ 行：第 $i+1$ 行包含一个整数：$H_i$。

输出格式

• 第 $1$ 行：一个整数，表示 Bessie 在接下来 $D$ 天中能达到的最高最低幸福值。
• 第 $2\sim N+1$ 行：第 $i+1$ 行包含一个整数，表示 Bessie 吃掉第 $i$ 块巧克力的日期。

5 5 
10 
40 
13 
22 
7 

24 
1 
1 
3 
4 
5 

提示

翻译由 DeepSeek 辅助完成。

Assisted translation by DeepSeek.