Repartiendo Caramelos.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

leo

Problem types

Allowed languages

Ada, Brain****, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, ~~Swift~~, VB

Los niños en un círculo infantil han recibido un gran saco que contiene $M$ ~M~ caramelos. Se ha decidido que los caramelos se distribuyan entre los $N$ ~N~ niños.

Cada niño ha indicado el número de caramelos que quiere. Si a un niño no se le da la cantidad de caramelos que quiere, se enojará. De hecho, se enfurecerá más por cada caramelo que le falte. Algunos especulan que su enojo será igual al cuadrado del número de caramelos de los que se le priva. Por ejemplo, si Julito declara que quiere 32 caramelos pero recibe sólo 29, le faltarían 3 caramelos, por lo que su enojo sería igual a 9.

Desafortunadamente, hay una cantidad insuficiente de caramelos para satisfacer a todos los niños. Por lo tanto, los dulces deben ser distribuidos de tal manera que la suma de el enojo de los niños sea mínima.

Entrada

La primera línea contiene dos números enteros, $M$ ~M~ y $N$ ~N~.
Las siguientes $N$ ~N~ líneas contienen números enteros (uno por línea) que representan los deseos de los niños. Todos esos números son estrictamente menores que $2*10^9$ ~2*10^9~, y su suma siempre excede $M$ ~M~.

Salida

La primera y única línea de salida debe contener la suma mínima del enojo de los niños.

Restricciones

$1 \leq M \leq 2*10^9$ ~1 \leq M \leq 2*10^9~
$1 \leq N \leq 100 000$ ~1 \leq N \leq 100 000~

Ejemplo #1 de Entrada

Ejemplo #1 de Salida

Ejemplo #2 de Entrada

Ejemplo #2 de Salida

Comments

-12

Primervirgen commented on Jan. 1, 2020, 11:14 p.m. ← edited →

.

This comment is hidden due to too much negative feedback. Show it anyway.

5

aniervs commented on Jan. 17, 2020, 3:43 a.m.

Si te fijas, este problema es de una Croatian Open Competition in Informatics (COCI). Búscalo y ya tendrás solución, código y casos de prueba, creo q es del primer contest del 2011 o del 2010.