2213 . 花枝遊戲

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

46.7% (7/15)

Submission's AC Ratio

17.7% (26/147)

Tags

CKcon 2021-CKcon

Description

作為這一屆花枝遊戲的負責人，你遇到了一個難題。
現在遊戲已經進入到最終階段，必須選出一名最終的贏家獲得所有的獎金。在這個遊戲裡面，有$n$個玩家要站在一排決鬥，並且在過程中他們的相對位置都不會改變。遊戲由數個回合組成，每個回合會將剩下的玩家分成左右兩半，之後左邊的每個玩家和右邊的每個玩家會依序決鬥。決鬥完後，由評審團選擇一邊的人留下，剩下的人全部淘汰。遊戲進行到剩下唯一一個人為止。

事實上，你知道這個遊戲是不公平的，因為台下的觀眾們只在乎遊戲的精彩度。你已經事先知道每個人的戰力值，從左至右數第$i$個人的戰力值為一個整數$a_i$。兩位玩家決鬥的精采度定義為他們戰力值的乘積，一回合的精彩度為每場決鬥的精彩度總和。也就是說，假設左邊玩家的戰力值為$l_1, l_2, ..., l_x$，右邊玩家的戰力值為$r_1, r_2, ..., r_y$，則該回合的精彩度為$\sum_{1 \leq i \leq x}\sum_{1 \leq j \leq y}l_i r_j$。你可以決定每回合左右邊玩家的分界點，也可以決定最後由哪邊取勝。而你希望最大化精彩度。

另外，觀眾們指定了$m$場想看的對決，每場對決的形式為$u, v$，代表一開始從左邊數第$u$位和第$v$位必須有一次決鬥。你想要知道在符合這些條件下的最大精彩度是多少。

Input Format

第一行有一個整數$t$，代表測資筆數。
每筆測資第一行有兩個整數$n, m$，代表人數和指定對決數。
第二行有$n$個整數$a_i$，代表每個人的戰力值。
接下來$m$行每行有兩個整數$u, v$，代表觀眾想看$u, v$的對決。
對於所有測資，$t \leq 5, n \leq 50000, m \leq 10000, |a_i| \leq 1000, 1 \leq u < v\leq n$
測資中$n$的總和不會超過$50000$。

Output Format

輸出$t$行，每行輸出一個整數，為最大可能的精彩度。

Sample Input 1

3
2 0
5 3
5 0
6 -4 -3 7 2
5 1
5 -3 5 -2 4
2 4

Sample Output 1

15
20
26

Hints

範測第二筆: 第一回合讓左邊兩人和右邊三人對決，精彩度為12，接下來淘汰左邊。第二回合讓剩餘的左邊兩人和右邊一人對決，精彩度為8，接下來淘汰左邊，留下最右邊一人。總精彩度為20。

Problem Source

TIOJ 1170

Subtasks

No. Testdata Range Constraints Score
1 0~4 $a_i \geq 0$ 6
2 5~13 $n \leq 10$ 9
3 14~28 $n \leq 400, m = 0$ 12
4 5~42 $n \leq 400$ 14
5 14~28, 43~56 $n \leq 5000, m = 0$ 21
6 0~70 $n \leq 5000$ 24
7 0~81 無其他限制 14

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 6 7
1 1000 131072 65536 1 6 7
2 1000 131072 65536 1 6 7
3 1000 131072 65536 1 6 7
4 1000 131072 65536 1 6 7
5 1000 131072 65536 2 4 6 7
6 1000 131072 65536 2 4 6 7
7 1000 131072 65536 2 4 6 7
8 1000 131072 65536 2 4 6 7
9 1000 131072 65536 2 4 6 7
10 1000 131072 65536 2 4 6 7
11 1000 131072 65536 2 4 6 7
12 1000 131072 65536 2 4 6 7
13 1000 131072 65536 2 4 6 7
14 1000 131072 65536 3 4 5 6 7
15 1000 131072 65536 3 4 5 6 7
16 1000 131072 65536 3 4 5 6 7
17 1000 131072 65536 3 4 5 6 7
18 1000 131072 65536 3 4 5 6 7
19 1000 131072 65536 3 4 5 6 7
20 1000 131072 65536 3 4 5 6 7
21 1000 131072 65536 3 4 5 6 7
22 1000 131072 65536 3 4 5 6 7
23 1000 131072 65536 3 4 5 6 7
24 1000 131072 65536 3 4 5 6 7
25 1000 131072 65536 3 4 5 6 7
26 1000 131072 65536 3 4 5 6 7
27 1000 131072 65536 3 4 5 6 7
28 1000 131072 65536 3 4 5 6 7
29 1000 131072 65536 4 6 7
30 1000 131072 65536 4 6 7
31 1000 131072 65536 4 6 7
32 1000 131072 65536 4 6 7
33 1000 131072 65536 4 6 7
34 1000 131072 65536 4 6 7
35 1000 131072 65536 4 6 7
36 1000 131072 65536 4 6 7
37 1000 131072 65536 4 6 7
38 1000 131072 65536 4 6 7
39 1000 131072 65536 4 6 7
40 1000 131072 65536 4 6 7
41 1000 131072 65536 4 6 7
42 1000 131072 65536 4 6 7
43 1000 131072 65536 5 6 7
44 1000 131072 65536 5 6 7
45 1000 131072 65536 5 6 7
46 1000 131072 65536 5 6 7
47 1000 131072 65536 5 6 7
48 1000 131072 65536 5 6 7
49 1000 131072 65536 5 6 7
50 1000 131072 65536 5 6 7
51 1000 131072 65536 5 6 7
52 1000 131072 65536 5 6 7
53 1000 131072 65536 5 6 7
54 1000 131072 65536 5 6 7
55 1000 131072 65536 5 6 7
56 1000 131072 65536 5 6 7
57 1000 131072 65536 6 7
58 1000 131072 65536 6 7
59 1000 131072 65536 6 7
60 1000 131072 65536 6 7
61 1000 131072 65536 6 7
62 1000 131072 65536 6 7
63 1000 131072 65536 6 7
64 1000 131072 65536 6 7
65 1000 131072 65536 6 7
66 1000 131072 65536 6 7
67 1000 131072 65536 6 7
68 1000 131072 65536 6 7
69 1000 131072 65536 6 7
70 1000 131072 65536 6 7
71 1000 131072 65536 7
72 1000 131072 65536 7
73 1000 131072 65536 7
74 1000 131072 65536 7
75 1000 131072 65536 7
76 1000 131072 65536 7
77 1000 131072 65536 7
78 1000 131072 65536 7
79 1000 131072 65536 7
80 1000 131072 65536 7
81 1000 131072 65536 7
Submit out of contest
Back to Top