В зоопарке Сингапура есть несколько кроликов. Чтобы накормить их, смотритель зоопарка купил $$$n$$$ морковок, имеющих длины $$$a_1, a_2, a_3, \ldots, a_n$$$. Кролики очень быстро размножаются. У смотрителя зоопарка сейчас есть $$$k$$$ кроликов и недостаточно морковок, чтобы прокормить их всех. Чтобы решить эту проблему, он решил разрезать морковки так, чтобы суммарно получилось $$$k$$$ кусков. По некоторой причине длины всех получившихся морковок должны быть положительными целыми числами.
Кролику очень сложно кушать длинную морковку, поэтому время, которое требуется, чтобы съесть морковку длины $$$x$$$, равно $$$x^2$$$.
Помогите смотрителю зоопарка разделить его морковки и найдите минимальное суммарное время, которое потребуется кроликам, чтобы их съесть.
В первой строке находятся два целых числа $$$n$$$ и $$$k$$$ $$$(1 \leq n \leq k \leq 10^5)$$$: изначальное количество морковок и количество кроликов.
В следующей строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^6)$$$: длины морковок.
Гарантируется, что сумма $$$a_i$$$ не меньше $$$k$$$.
Выведите одно целое число: минимальное суммарное время, которое потребуется кроликам, чтобы съесть морковки при каком-то их разделении.
3 6 5 3 1
15
1 4 19
91
Для первого теста оптимальные размеры морковок это $$$\{1,1,1,2,2,2\}$$$. Время, которое потребуется, чтобы съесть эти морковки, равно $$$1^2+1^2+1^2+2^2+2^2+2^2=15$$$.
Для второго теста оптимальные размеры морковок это $$$\{4,5,5,5\}$$$. Время, которое потребуется, чтобы съесть эти морковки, равно $$$4^2+5^2+5^2+5^2=91$$$.
Название |
---|