问题 23765 --小烈上菜

23765: 小烈上菜

时间限制: 1 Sec  内存限制: 128 MB
提交: 107  解决: 30
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][104kb]

题目描述

小烈一下碰碰车就被乐满地的工作人员抓住了。作为扰乱秩序的惩罚,小烈必须去乐满地里的“漓江村”饭店端盘子。服务员的工作很繁忙。他们要上菜,同时要使顾客们尽量高兴。一位服务生为n 个顾客上菜。这n 个顾客坐成一排,小烈从一端的厨房中端出n 盘菜(不要问我为什么小烈能一下子端住2500 盘菜,他就是能。),为n 个顾客各上一道相同的菜。显然,小烈需要走一个来回,如图:

      本来,小烈可以按1,2,3……n 的顺序一次给每个顾客上菜,但是,聪明的小烈通过观察发现,每个顾客都有一个开心值H1,H2,H3……,Hn ,离厨房最近的为H1,然后依次为H2,H3……,Hn。若小烈给第j 位顾客上菜前刚刚为第i 位顾客上菜,则第j 位就会高兴,产生高兴指数Wj=Hi×Hj 。这样,如果小烈按一定的方式调整上菜顺序,可以得到更高的高兴指数。现在小烈想知道用某一方法可达到的n 位顾客高兴指数之和的最大值S。因为顾客越高兴,给小烈的小费越多。第一位上菜的顾客不产生高兴值


输入

第一行一个数,n,顾客的数目
第二行n 个数,第i 个数表示第i 位顾客的开心值。各个数字用空格隔开。

输出

一个数s,为高兴指数的最大值

样例输入

3
7 1 9

样例输出

72

提示

【样例说明】

从左往右上1 的菜,再上9 的菜,高兴值是0*1+1*9,从右往左走回来的时候上7 的菜,高

兴值是7*9,总的高兴值就是72。

【数据规模】

对于30%的数据n≤9,n∈N+

对于70%的数据n≤1500,n∈N+

对于100%的数据n≤2500,n∈N+

所有数字小于(含结果)

2147483648

来源

[提交][状态]