1170 . 競技場 (Arena)
TopCoder
Tags
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 1
4
1 -2 3 5
1 -2 3 5
Sample Output 1
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 |