TopCoder

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

12.5% (3/24)

Tags

Description

在遙遠的東方,有個安居樂業的小國家,稱為「櫸共和國」。
在共和國的首都,有座名聞遐邇的私立櫸學園。這座學校以高偏差值著稱,師資、設備等都相當完備。
不過,更為著名的是它的學生們。這些學生個個有著標緻的面容,並多才多藝,除了唱歌跳舞外,有些學生甚至連馬術、書法都十分擅長。
故事發生在即將自櫸學園畢業的泉子身上

今天,櫸學園的所有學生聚集起來,一起歡送泉子的畢業。
學校準備了一個$1\times n$的蛋糕,讓大家一起享用。
單純的吃這塊蛋糕實在太無聊了,大家決定把他切成若干段,每次選最前面和最後面的那兩段來享用(因此只能切成偶數段)。
(每段蛋糕的長寬都是正整數)
正好,這塊長型蛋糕的每一單位長都被賦予了一個美味值
(由於學校經費不足,所以可能買到品質差的蛋糕,導致美味值有可能為零,甚至是負的)。
而每一段蛋糕的美味值是內部所有美味值的加總,而每次一起吃的美味值是兩段蛋糕的美味值乘積。
這條蛋糕的總美味值就是所有乘積的加總。
請你幫幫櫸學員的大家,告訴他們這塊蛋糕可以多好吃。

Input Format

輸入有兩行,第一行含有一個正整數$n\geq 2$
第二行有$n$個整數$a_1 \dots a_n$

Testdata Score Constraint
Subtask 1 0~9 10 $n\leq100,\ |a_i|\leq10$
Subtask 2 10~14 20 $n\le100,\ |a_i|\leq1000$
Subtask 3 15~29 30 $n\le 500,\ |a_i|\leq10^6$
Subtask 4 30~39 40 $n\le 750,\ |a_i|\leq10^6$

Output Format

輸出一行,包含一個整數,表示這條蛋糕在任意切法下,所得到的最高美味值。

Sample Input

#Test Case 1
5
-7 1 -1 0 -4

#Test Case 2
6
1 2 3 -4 -5 -6

#Test Case 3
7
1 2 -3 -4 -5 4 2

Sample Output

#Test Case 1
30

#Test Case 2
18

#Test Case 3
53

Hints

範測最好方法是
Test Case 1
-7 1 | -1 0 -4

Test Case 2
1 2 3 -4 -5 | -6

Test Case 3
1 2 | -3 -4 | -5 | 4 2

Problem Source

Problem set and Description by erd1
今泉佑唯畢業快樂

Subtasks

For Testdata: 0 ~ 9, Score: 10
For Testdata: 10 ~ 14, Score: 20
For Testdata: 15 ~ 29, Score: 30
For Testdata: 30 ~ 39, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536
20 1000 65536 65536
21 1000 65536 65536
22 1000 65536 65536
23 1000 65536 65536
24 1000 65536 65536
25 1000 65536 65536
26 1000 65536 65536
27 1000 65536 65536
28 1000 65536 65536
29 1000 65536 65536
30 1500 65536 65536
31 1500 65536 65536
32 1500 65536 65536
33 1500 65536 65536
34 1500 65536 65536
35 1500 65536 65536
36 1500 65536 65536
37 1500 65536 65536
38 1500 65536 65536
39 1500 65536 65536