← 返回题目列表

Codeforces · 1248/B

B. 种树

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

园丁阿列克谢向高中生教授竞争性编程。为了祝贺阿列克谢教师节,学生们送给他一系列木棍,每根木棍的长度都是整数。现在阿列克谢想用它们长成一棵树。

这棵树看起来像平面上的一条折线,由所有木棍组成。多段线从点 $$$(0, 0)$$$ 开始。在构建折线时,Alexey 将以任意顺序将木棍一根一根地固定在其上。每根棍子必须是垂直或水平的(即平行于 $$$OX$$$ 或 $$$OY$$$ 轴)。不允许两个连续的木棍同时水平对齐或同时垂直对齐。请参阅下图以了解详情。

Alexey 想要制作一条折线,使其末端尽可能远离 $$$(0, 0)$$$。请帮助他以这种方式种植这棵树。

请注意,定义树形式的折线可能具有自交和自接触,但可以证明最佳答案不包含任何自交或自接触。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — Alexey 作为礼物得到的木棍数量。

第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10\,000$$$) — 木棍的长度。

输出

打印一个整数 - 从 $$$(0, 0)$$$ 到树末端的最大可能距离的平方。

示例

输入 #1

3
1 2 3

输出 #1

26

输入 #2

4
1 1 2 2

输出 #2

20

注意

下图显示了示例测试的最佳树。第一个示例中的平方距离等于 $$$5 \cdot 5 + 1 \cdot 1 = 26$$$,第二个示例中的平方距离等于 $$$4 \cdot 4 + 2 \cdot 2 = 20$$$。