← 返回题目列表

Codeforces · 1106/C

C. 农历新年和数字除法

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

农历新年即将来临,鲍勃正在为他的家庭作业而苦苦挣扎——一道数除法问题。

Bob 的作业纸上有 $$$n$$$ 正整数 $$$a_1, a_2, \ldots, a_n$$$,其中 $$$n$$$ 始终为偶数。 Bob 被要求将这些数字分成几组,每组必须至少包含 $$$2$$$ 数字。假设将数字分为 $$$m$$$ 组,第 $$$j$$$ 组中的数字之和为 $$$s_j$$$。 Bob 的目标是最小化 $$$s_j$$$ 的平方和,即 $$$$$$\sum_{j = 1}^{m} s_j^2.$$$$$$

鲍勃对这个难题感到困惑。你能帮他解决一下吗?

输入

第一行包含一个偶数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$),表示 Bob 的作业纸上有 $$$n$$$ 个整数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^4$$$),描述需要处理的数字。

输出

一行包含一个整数,表示$$$s_j$$$的平方和的最小值,即$$$$$$\sum_{i = j}^{m} s_j^2,$$$$$$,其中$$$m$$$是组数。

示例

输入 #1

4
8 5 2 3

输出 #1

164

输入 #2

6
1 1 1 2 2 2

输出 #2

27

注意

在第一个示例中,最佳解决方案之一是将这些 $$$4$$$ 数字分为 $$$2$$$ 组 $$$\{2, 8\}, \{5, 3\}$$$。因此答案是 $$$(2 + 8)^2 + (5 + 3)^2 = 164$$$。

在第二个示例中,最佳解决方案之一是将这些 $$$6$$$ 数字分为 $$$3$$$ 组 $$$\{1, 2\}、\{1, 2\}、\{1, 2\}$$$。因此答案是 $$$(1 + 2)^2 + (1 + 2)^2 + (1 + 2)^2 = 27$$$。