TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 $$AC \approx (111111111)_2$$

User's AC Ratio

94.6% (35/37)

Submission's AC Ratio

45.6% (52/114)

Description

在遙遠的天龍國,有一場格鬥競技賽正如火如荼地進行中。然而時間剩不多了,尚未被淘汰的參賽者卻還很多。為了加快比賽的進行,主辦方決定使用以下的形式進行接下來的比賽。
一開始,先讓ܰ名選手站在台上排成一列。接著,主辦方會決定界於某兩名選手之間的界線,並讓左右兩邊的選手對打,使得對於任何一個在左邊的選手 $A$ 以及在右邊的選手 $B$, $A$ 跟 $B$ 都恰交手過一次。對打結束後,由主辦方決定要淘汰掉左邊還是右邊的所有選手,再讓所有未被淘汰的選手站回原位,繼續此流程,直至冠軍產生。如此一來,可以有多場比賽同時進行,便可加快比賽流程。
然而加快比賽流程便意味著比賽的「精彩度」下降。為了彌補這個缺失,主辦方決定最大化比賽精彩度的總和。對於兩個人 $A, B$,若他們的實力值分別是 $a, b$ 那麼他們兩個對決
的精彩度便是 $a \times b$ ,也就是兩人實力值之積。
請你寫一個程式,計算所有比賽的精彩度總和最大可以是多少。
原始題目 PDF

Input Format

第一行包含一個正整數 $N$,代表選手個數。第二行包含ܰ個整數 $a_1,a_2,\cdots,a_n$ 代表從左至右選手的實力值大小。

Output Format

請輸出一行包含一個整數,代表精彩度總和的最大值。

Sample Input

4
1 -2 3 5

Sample Output

11

Hints

Problem Source

Problem Set / Description by Paupière
建國中學105學年度北市賽模擬賽pA

Subtasks

No. Testdata Range Constraints Score
1 0~2 $N \leq 1000, a_i = 1$ 10
2 3~4 $N \leq 1000, 0 \leq a_i \leq 30$ 10
3 5~9 $N \leq 10, |a_i| \leq 30$ 10
4 5~14 $N \leq 100, |a_i| \leq 30$ 20
5 0~17 $N \leq 1000, |a_i| \leq 30$ 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 524288 262144 1 5
1 3000 524288 262144 1 5
2 3000 524288 262144 1 5
3 3000 524288 262144 2 5
4 3000 524288 262144 2 5
5 3000 524288 262144 3 4 5
6 3000 524288 262144 3 4 5
7 3000 524288 262144 3 4 5
8 3000 524288 262144 3 4 5
9 3000 524288 262144 3 4 5
10 3000 524288 262144 4 5
11 3000 524288 262144 4 5
12 3000 524288 262144 4 5
13 3000 524288 262144 4 5
14 3000 524288 262144 4 5
15 3000 524288 262144 5
16 3000 524288 262144 5
17 3000 524288 262144 5