Задача №115144. Подземелья Одинокой горы
Однажды люди, эльфы, гномы и другие жители Средиземья собрались отнять у Смога украденные у них сокровища. Во имя этой великой цели они сплотились вокруг сильного эльфа Тимофея и начали планировать свержение правителя Одинокой горы.
Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы , которые находятся в разных отрядах, прибавляет \(b\) единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из \(k\) отрядов, уменьшается на \((k - 1) \cdot X\) единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда .
Известно, что в Средиземье проживают \(n\) рас, и количество существ \(i\)-й расы равно \(c_i\). Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.
Первая строка входных данных содержит три целых числа \(n\), \(b\) и \(X\) (\(1 \le n \le 200\,000\), \(1 \le b \le 10^6\), \(0 \le X \le 10^9\)) — количество рас и константы \(b\) и \(X\), описанные выше.
Вторая строка содержит \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 200\,000\)) — количество существ каждой из \(n\) рас.
Гарантируется, что \(c_1 + c_2 + \ldots + c_n \le 200\,000\).
Выведите одно целое число — максимальную силу армии, которую могут составить жители Средиземья.
Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.
В данной задаче \(50\) тестов, помимо тестов из условия. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(X = 0\), наберут не менее \(16\) баллов.
Решения, корректно работающие при \(n = 1\), наберут не менее \(10\) баллов.
Решения, корректно работающие при \(n \le 2\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(c_1 = c_2 = \ldots = c_n\), наберут не менее \(14\) баллов.
Решения, корректно работающие при \(c_1 + c_2 + \ldots + c_n \leq 2000\), наберут не менее \(18\) баллов.
В первом примере жители Средиземья могут составить \(3\) отряда. Так как \(X = 0\), то сила армии не уменьшится из-за количества отрядов. Далее жителей по отрядам можно распределить так:
-
Единственного представителя первой расы можно отправить в первый отряд.
-
Первого представителя второй расы можно отправить в первый отряд, второго представителя второй расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на \(b = 1\).
-
Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на \(3 \cdot b = 3\), так как они образуют три пары, находящиеся в разных отрядах.
Таким образом, суммарная сила армии равна \(4\).
3 1 0 1 2 3
4
3 5 10 2 5 3
40