Даны два массива $$$a$$$ и $$$b$$$ длины $$$n$$$.
Вы можете любое количество раз (возможно, ноль) выполнить следующую операцию: выбрать индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и поменять местами $$$a_i$$$ и $$$b_i$$$.
Назовем стоимостью массива $$$a$$$ величину, равную $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2$$$. Аналогично, стоимость массива $$$b$$$ будет равна $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (b_i + b_j)^2$$$.
Вам необходимо минимизировать суммарную стоимость двух массивов.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 40$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержится целое число $$$n$$$ ($$$1 \leq n \leq 100$$$) — длина обоих массивов.
Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — элементы первого массива.
В третей строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 100$$$) — элементы второго массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$100$$$.
Для каждого набора входных данных выведите минимальную возможную суммарную стоимость двух массивов.
313643 6 6 62 7 4 146 7 2 42 5 3 5
0 987 914
Во втором наборе входных данных в одном из оптимальных ответов после выполнения операций $$$a = [2, 6, 4, 6]$$$, $$$b = [3, 7, 6, 1]$$$.
Стоимость массива $$$a$$$ равна $$$(2 + 6)^2 + (2 + 4)^2 + (2 + 6)^2 + (6 + 4)^2 + (6 + 6)^2 + (4 + 6)^2 = 508$$$.
Стоимость массива $$$b$$$ равна $$$(3 + 7)^2 + (3 + 6)^2 + (3 + 1)^2 + (7 + 6)^2 + (7 + 1)^2 + (6 + 1)^2 = 479$$$.
Суммарная стоимость массивов равна $$$508 + 479 = 987$$$.
| Codeforces Global Round 19 |
|---|
| Закончено |
