Задача №115405. Арифметическое упражнение
Вам дается массив \(a\) длины \(n\), в котором изначально все значения равны нулю. Также вам передано \(m\) чисел \(x_1,\ x_2,\ \ldots\ x_m\). Далее вы последовательно для каждого \(i\) от \(1\) до \(m\) выбираете некоторый индекс \(j_i\) и делаете изменение \(a_{j_i} = x_i - a_{j_i}\).
Помогите Олегу с Дашей узнать, какую максимальную сумму элементов массива \(a\) можно получить после всех изменений, если делать выбор оптимально.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число \(t\) (\(1 \le t \le 10\,000\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 300\,000\)) — длину массива \(a\) и количество значений \(x_i\) соответственно.
Вторая строка каждого набора входных данных содержит \(m\) целых чисел \(x_1\), \(x_2\), \(\ldots\), \(x_m\) (\(-10^9 \le x_i \le 10^9\)) — описание значений.
Обозначим за \(N\) сумму \(n\) по всем наборам входных данных, а за \(M\) сумму \(m\) по всем наборам входных данных.
Гарантируется, что \(N\) и \(M\) не превосходят \(300\,000\).
Для каждого набора входных данных в отдельной строке выведите единственное число — максимальную сумму массива \(a\), которую можно получить.
В первом наборе входных данных все операции применяются к первому элементу массива \(a\), он последовательно равен \(1 - 0 = 1\), \(2 - 1 = 1\), \(3 - 1 = 2\), \(4 - 2 = 2\), поэтому ответ равен \(2\).
Во втором наборе входных данных можно выполнить следующую последовательность изменений:
- Применим изменение к первому элементу \(a_1 = 10 - a_1 = 10 - 0 = 10\), \(a = [10, 0]\).
- Применим изменение к первому элементу \(a_1 = 3 - a_1 = 3 - 10 = -7\), \(a = [-7, 0]\).
- Применим изменение к первому элементу \(a_1 = 7 - a_1 = 7 - (-7) = 14\), \(a = [14, 0]\).
- Применим изменение к первому элементу \(a_1 = 1 - a_1 = 1 - 14 = -13\), \(a = [-13, 0]\).
- Применим изменение ко второму элементу \(a_2 = 4 - a_2 = 4 - 0 = 4\), \(a = [-13, 4]\).
- Применим изменение к первому элементу \(a_1 = 6 - a_1 = 6 - (-13) = 19\), \(a = [19, 4]\).
- Применим изменение ко второму элементу \(a_2 = 3 - a_2 = 3 - 4 = -1\), \(a = [19, -1]\).
В конце имеем \(a = [19, -1]\), поэтому итоговая сумма равна \(18\).
Можно показать, что добиться лучшего ответа нельзя.
Тесты к этой задаче состоят из десяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n, N\) | \(m, M\) | \(x_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия |
| 1 | 4 | – | – | \(0 \le x_i\) | – | Все \(x_i\) равны |
| 2 | 8 | \(n=2\) | \(M \le 30\) \(m \le 18\) | – | – | |
| 3 | 11 | \(n=2\) | \(M \le 50\) | \(-10 \le x_i \le 10\) | – | |
| 4 | 9 | \(n=2\) | \(M \le 400\) | \(-400 \le x_i \le 400\) | 3 | |
| 5 | 8 | \(N \le 30\) \(n \le 18\) | \(M \le 30\) \(m \le 18\) | – | 0 | |
| 6 | 10 | \(N \le 2000\) | \(M \le 2000\) | \(0 \le x_i\) | – | |
| 7 | 12 | \(N \le 2000\) | \(M \le 2000\) | – | 0, 2 – 6 | |
| 8 | 10 | – | – | \(0 \le x_i\) | 1 | Среди \(x_i\) не более двух различных значений |
| 9 | 17 | – | – | \(0 \le x_i\) | 1, 6, 8 | |
| 10 | 11 | – | – | – | 0 – 9 | Offline-проверка. |
4 1 4 1 2 3 4 2 7 10 3 7 1 4 6 3 4 10 103 354 1 227 179 189 142 201 165 140 5 3 -10 11 -4
2 18 1085 17