P6236 [COCI 2010/2011 #1] LJUTNJA

Kindergarten children received a big package with $m$ candies, and now these candies need to be distributed to $n$ children. Each child has given an expected number of candies. If a child does not receive their expected amount $a_i$, the child will get angry. For each missing candy, the child’s anger increases. You can assume the anger level equals the square of the number of candies they are short of. For example, Mirko wants to get $32$ candies but only gets $29$. He is short of $3$, so his anger level is $9$. Unfortunately, there are not enough candies to satisfy all children’s expectations. Therefore, we should choose an optimal distribution method so that the sum of all children’s anger levels is minimized.

The input has $n+1$ lines. The first line contains two integers $m, n$. The next $n$ lines each contain one integer. The integer on line $i+1$ is the expected value $a_i$ of the $i$-th child.

The output has one line. Output one integer, which is the minimum total anger level.

#### Explanation for Sample Input/Output 1 There are $10$ candies and $4$ people. Give each child the number of candies they want minus $1$, that is, give $3, 4, 1, 2$ candies respectively. Then each person is short of one candy, so each person’s anger level is $1^2 = 1$. With $4$ people, the total is $1 \times 4 = 4$. The answer $4$ is optimal. --- #### Constraints - For $40\%$ of the testdata, $n \leq 5000$, $m \leq 30$, and the result does not exceed $5 \times 10^8$. - For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq m \leq 2 \times {10}^9$, and the result does not exceed $2^{64}-1$. Translated by ChatGPT 5