#P1948. Triangular Pastures

Triangular Pastures

题目描述:

和所有人一样,奶牛也喜欢多样化。它们目前的喜好是牧场的新形状。古老的长方形牧场已经失宠,新的几何形状才是它们的最爱。伊姆・黑(I.M.HeiI.M. Hei)是奶牛牧场的首席建筑师,她负责设计一个被漂亮白色围栏围起来的三角形牧场。她有NN (3N403 \leq N \leq 40)段围栏,每段围栏长度为整数 LiLi (1Li401 \leq L_i \leq 40),并且必须把这些围栏段拼成一个三角形牧场,使其拥有最大的可放牧面积。黑女士必须使用所有的围栏段来构成三条长度不为零的边。请帮助黑女士让牛群中的其他成员相信,将会有充足的放牧空间。计算用给定的一组围栏段所能围成的最大面积。

输入:

11 行输入一个单独的整数 NN

22 行到第 N+1N + 1 行,共 NN 行,每行都有一个单独的整数,表示一段围栏的长度。这些长度不一定是各不相同的。

输出:

输出单独的一行,包含一个整数,该整数是将可能围成的最大面积乘以 100100 后取整得到的结果。如果无法构建出面积为正数的三角形,则输出 1-1

输入数据1

5
1
1
3
3
4

输出数据1

692

提示:

它是边长为 44 的等边三角形面积的 100100

来源:

美国计算机奥林匹克竞赛(USACO)2002 年 2 月赛