背景

5s 512M

题目描述

给定一个包含 $n$ 个整数的数组 $a$。每次操作中，你可以选择一个位置 $i$（$1 \leq i \leq n$），将 $a_i$ 减少 $k$，同时将所有其他元素 $a_j$（$1 \leq j \leq n$ 且 $i \neq j$）增加 $t$。

求将数组中所有元素变为非正数（即小于或等于零）所需的最少操作次数。如果无法实现，则报告该情况。

输入格式

第一行包含三个整数 $n$、$k$、$t$（$1 \leq n \leq 10^6$，$0 \leq k, t \leq 10^9$）——数组长度及操作参数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^{18} \leq a_i \leq 10^9$）——数组元素的初始值。

输出格式

输出一个整数 $c$——将数组所有元素变为非正数所需的最少操作次数。如果无法实现，输出 $-1$。

如果可以实现，还需输出 $n$ 个整数 $cnt_i$（$1 \leq i \leq n$），表示对第 $i$ 个元素执行的操作次数。注意必须满足 $\sum\limits_{i=1}^n cnt_i = c$。

4 10 1
2 5 9 -4

4
1 1 2 0 

5 1 100
-1000 -1000 10 -1000 -1000

10
0 0 10 0 0 

2 1 1
1 0

-1

提示

• （$3$ 分）$t = 0$；
• （$5$ 分）$1 \leq n \leq 300$，$0 \leq |a_i| \leq 300$，$0 \leq t \leq 10^6$；
• （$8$ 分）$1 \leq n \leq 3000$，$0 \leq |a_i| \leq 3000$，$0 \leq t \leq 10^6$；
• （$9$ 分）$1 \leq n \leq 10^3$，$1 \leq a_i \leq 10^9$，$0 \leq t \leq 10^6$；
• （$5$ 分）$1 \leq n \leq 10^4$，$1 \leq a_i \leq 10^9$；
• （$13$ 分）$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$；
• （$8$ 分）$1 \leq a_i \leq 10^9$；
• （$9$ 分）$1 \leq n \leq 10^3$，$0 \leq t \leq 10^6$；
• （$5$ 分）$1 \leq n \leq 10^4$；
• （$14$ 分）$1 \leq n \leq 10^5$；
• （$21$ 分）无额外限制。

翻译由 DeepSeek V3 完成