3855: 2014宁波市中小学生程序设计竞赛(小学组)复赛 第4题 小李打怪兽

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:7 通过:3

题目描述

  小李对故乡的思念全部化作了对雾霾天气的怨念,这引起了掌控雾霾的邪神的极大不满,邪神派去了一只小怪兽去对付小李,由于这只怪兽拥有极高的IQ,它觉得直接消灭小李太没有难度了,它决定要和小李在智力水平上一较高下。我们可否帮助小李来战胜强大的怪兽呢?
  问题是这样的:给定一堆正整数,要求你分成两堆,两堆数的和分别为S1和S2,谁分的方案使得S1*S1-S2*S2的结果小(规定S1>=S2),谁就将获得胜利。
注:S2可以等于0。

输入格式

  第一行n,表示共有n个数

  第二行共n个用空格隔开的正整数ai,表示给定的一堆正整数。


【样例说明】
  1和4一堆,2和3一堆,5*5-5*5 = 0
【数据规模】
  60%的数据,1<=n<=20
  80%的数据,1<=n<=50,ai<=20
  100%的数据,1<=n<=100,ai<=100

输出格式

输出就一个整数,表示S1*S1-S2*S2的最小值。

输入样例 复制

4
1 2 3 4

输出样例 复制

0