← 返回题目列表

Codeforces · 1637/D

D. 又一个最小化问题

中文机器翻译题面 查看原题

给定两个数组 $$$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$$$。

输出

对于每个测试用例,打印可能的最小总成本。

示例

输入 #1

3
1
3
6
4
3 6 6 6
2 7 4 1
4
6 7 2 4
2 5 3 5

输出 #1

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$$$。