作為這一屆花枝遊戲
的負責人,你遇到了一個難題。
現在遊戲已經進入到最終階段,必須選出一名最終的贏家獲得所有的獎金。在這個遊戲裡面,有$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$位必須有一次決鬥。你想要知道在符合這些條件下的最大精彩度是多少。
第一行有一個整數$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$。
輸出$t$行,每行輸出一個整數,為最大可能的精彩度。
範測第二筆: 第一回合讓左邊兩人和右邊三人對決,精彩度為12,接下來淘汰左邊。第二回合讓剩餘的左邊兩人和右邊一人對決,精彩度為8,接下來淘汰左邊,留下最右邊一人。總精彩度為20。
TIOJ 1170
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 |