P12636 [UOI 2020] Array Reduction

Given an array $a$ consisting of $n$ integers. For one operation, you can choose position $i$ ($1 \leq i \leq n$), decrease $a_i$ by $k$, and increase the value of all other elements $a_j$ ($1 \leq j \leq n, i \neq j$) by $t$. Find the minimum number of operations needed to make all elements of the array less than or equal to zero (i.e., non-positive), or report that it is impossible to do so.

The first line contains three integers $n$, $k$, $t$ ($1 \leq n \leq 10^6$, $0 \leq k, t \leq 10^9$) --- the length of the array and the operation parameters. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^{18} \leq a_i \leq 10^9$) --- the initial values of the array elements.

Output a single integer $c$ --- the minimum number of operations needed to make all elements of the array less than or equal to zero. If it is impossible, output $-1$. If it is possible, output $n$ integers $cnt_i$ ($1 \leq i \leq n$), which represent the number of operations performed on the element with index $i$. Note that the equality $\sum\limits_{i=1}^n cnt_i = c$ must hold.

- ($3$ points) $t = 0$; - ($5$ points) $1 \leq n \leq 300, 0 \leq |a_i| \leq 300, 0 \leq t \leq 10^6$; - ($8$ points) $1 \leq n \leq 3000, 0 \leq |a_i| \leq 3000, 0 \leq t \leq 10^6$; - ($9$ points) $1 \leq n \leq 10^3, 1 \leq a_i \leq 10^9, 0 \leq t \leq 10^6$; - ($5$ points) $1 \leq n \leq 10^4, 1 \leq a_i \leq 10^9$; - ($13$ points) $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$; - ($8$ points) $1 \leq a_i \leq 10^9$; - ($9$ points) $1 \leq n \leq 10^3, 0 \leq t \leq 10^6$; - ($5$ points) $1 \leq n \leq 10^4$; - ($14$ points) $1 \leq n \leq 10^5$; - ($21$ points) without additional constraints.