P16544 [EGOI 2026] Cake / Cakes

Liliana’s birthday is coming, and she has invited all her best friends to celebrate. To make the party more special, she plans to prepare several cakes, each decorated with various toppings such as strawberries, almonds, or praline. Liliana has $N$ types of toppings, and for each topping $i$ she has $a_i$ pieces. A cake’s “deliciousness” is defined as the maximum number of occurrences of any single topping on that cake. For example: - If a cake has toppings ${1, 1, 2, 2, 2}$, then its deliciousness is $3$, because topping $2$ appears three times. - If a cake has toppings ${0, 0, 1, 1, 2}$, then its deliciousness is $2$, because both topping $0$ and topping $1$ appear twice, and no other topping appears more times. Liliana wants to bake several cakes that all have the same deliciousness, and she must use **all toppings** with nothing left over. She has not decided how many cakes to bake. She is considering $Q$ plans, each plan specifying a number of cakes $K_j$. For each plan, determine whether it is possible to distribute all toppings among $K_j$ cakes such that every cake has the same deliciousness. The total number of toppings on each cake may be different, but each cake must contain at least one topping. Note that different cakes may contain different numbers of topping types.

The first line contains two integers $N$ and $Q$, representing the number of topping types and the number of plans. The second line contains $N$ integers $a_0, a_1, \dots, a_{N-1}$, where $a_i$ is the number of pieces of topping $i$. The next $Q$ lines each contain one integer $K_j$, specifying the number of cakes required in the $j$-th plan.

Output $Q$ lines. If it is possible to distribute all toppings among $K_j$ cakes with the same deliciousness, output `YES` on the $j$-th line; otherwise output `NO`.

### Sample Explanation In the first sample, Liliana has four topping types: two pieces of topping 0 (shown as green triangles), five pieces of topping 1 (shown as yellow stars), one piece of topping 2 (shown as an orange circle), and one piece of topping 3 (shown as a blue square). When $K = 1$, Liliana can make one cake with deliciousness $5$ by putting all toppings on a single cake: - Cake 1: $\{0, 0, 1, 1, 1, 1, 1, 2, 3\}$ (topping 1 appears five times). :::align{center}  An example distribution for $K = 1$. ::: When $K = 2$, Liliana cannot distribute all toppings into two cakes with the same deliciousness. When $K = 3$, Liliana can make $3$ cakes, each with deliciousness $2$, distributed as follows: - Cake 1: ${0, 0, 1}$ (topping 0 appears twice). - Cake 2: ${1, 1, 2}$ (topping 1 appears twice). - Cake 3: ${1, 1, 3}$ (topping 1 appears twice). :::align{center}  An example distribution for $K = 3$. ::: When $K = 4$, Liliana cannot distribute all toppings into four cakes with the same deliciousness. When $K = 5$, Liliana can make $5$ cakes, each with deliciousness $1$, distributed as follows: - Cake 1: ${0, 1}$ (topping 0 and topping 1 each appear once). - Cake 2: ${0, 1}$ (topping 0 and topping 1 each appear once). - Cake 3: ${1}$ (topping 1 appears once). - Cake 4: ${1, 2}$ (topping 1 and topping 2 each appear once). - Cake 5: ${1, 3}$ (topping 1 and topping 3 each appear once). :::align{center}  An example distribution for $K = 5$. ::: ### Constraints - $1 \leq N, Q \leq 100\ 000$. - $1 \leq a_i \leq 100\ 000$. - $1 \leq K_j \leq 10^{18}$. ### Scoring Your program will be tested on testdata divided into several subtasks. To get the score for a subtask, you must solve all the testdata in that subtask correctly. - **Subtask $0$** [$0$ points]: Samples. - **Subtask $1$** [$9$ points]: $N = 1$. - **Subtask $2$** [$22$ points]: $Q = 1$ and $K_j = 2$. - **Subtask $3$** [$24$ points]: $Q \le 5, N \le 1000, a_i \le 1000$. - **Subtask $4$** [$24$ points]: $Q \le 5$. - **Subtask $5$** [$21$ points]: No additional constraints. Translated by ChatGPT 5