← 返回题目列表

Codeforces · 1344/D

D. 简历回顾

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

呃哦!科技公司的申请即将截止,而你却因为参加比赛而拖延了时间! (现在让我们假设在这个不确定的时期实际上是有可能找到工作的。)

您已经完成了许多编程项目。事实上,编程项目总共有 $$$n$$$ 种类型,并且您已经完成了 $$$a_i$$$ 类型为 $$$i$$$ 的项目。你的简历空间有限,但你需要仔细选择它们,以最大限度地提高你被录用的机会。

您希望包含多个相同类型的项目以强调您的专业知识,但您也不希望包含太多,以免低质量项目开始出现。具体而言,您确定以下数量作为您被录用机会的良好指标:

$$$$$$ f(b_1,\ldots,b_n)=\sum\limits_{i=1}^n b_i(a_i-b_i^2)。 $$$$$$

这里,$$$b_i$$$ 表示您的简历中包含的 $$$i$$$ 类型的项目数量。当然,您不能包含比已完成的项目更多的项目,因此您需要 $$$0\le b_i \le a_i$$$ 来表示所有 $$$i$$$。

你的简历只够容纳$$$k$$$项目,如果你的简历有空,你绝对不会被录用,所以你需要$$$\sum\limits_{i=1}^n b_i=k$$$。

查找 $$$b_1,\ldots, b_n$$$ 的值,使 $$$f(b_1,\ldots,b_n)$$$ 的值最大化,同时满足上述两个约束。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le n\le 10^5$$$, $$$1\le k\le \sum\limits_{i=1}^n a_i$$$)——分别是编程项目的类型数量和简历大小。

下一行包含 $$$n$$$ 整数 $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — $$$a_i$$$ 等于 $$$i$$$ 类型的已完成项目数。

输出

在单行中输出$$$n$$$整数$$$b_1,\ldots, b_n$$$,其达到$$$f(b_1,\ldots,b_n)$$$的最大值,同时满足要求$$$0\le b_i\le a_i$$$和$$$\sum\limits_{i=1}^n b_i=k$$$。如果有多个解,则输出任意一个。

请注意,您不必输出值 $$$f(b_1,\ldots,b_n)$$$。

示例

输入 #1

10 32
1 2 3 4 5 5 5 5 5 5

输出 #1

1 2 3 3 3 4 4 4 4 4

输入 #2

5 8
4 4 8 2 1

输出 #2

2 2 2 1 1

注意

对于第一个测试,最佳答案是 $$$f=-269$$$。请注意,如果我们忽略约束 $$$\sum\limits_{i=1}^n b_i=k$$$,则可能会出现更大的 $$$f$$$ 值。

对于第二个测试,最佳答案是 $$$f=9$$$。