1170 . 競技場 (Arena)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

95.2% (60/63)

Submission's AC Ratio

43.2% (111/257)

Tags

CKsim 2016-CKsim-北市模擬

Description

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

Input Format

第一行包含一個正整數 N，代表選手個數。第二行包含ܰ個整數 a1,a2,⋯,an 代表從左至右選手的實力值大小。

Output Format

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

Sample Input 1

4
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≤1000,ai=1 10
2 3~4 N≤1000,0≤ai≤30 10
3 5~9 N≤10,|ai|≤30 10
4 5~14 N≤100,|ai|≤30 20
5 0~17 N≤1000,|ai|≤30 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Submit
Back to Top