All submissions for this problem are available.Tweedledee and Tweedledum are in a fierce battle playing a complicated graph game. The game is played on an undirected bidirectional simple graph of $N$ vertices (enumerated $1$ trhough $N$) and $(N \cdot (N-1))/2$ edges. We'll denote the beauty of vertex $u$ by $B_u$. The game goes as follows: - First Twedledee places a token in one of the vertices of the graph. - Then players alternate turns, Tweedledum goes first. - In their turn a player must move the token to another vertex following one of its adjacent edges, the turn is finished by removing that edge. - After moving the token from one vertex to another, let's say from $u$ to $v$, the beauty of the game increases by $B_u \cdot B_v$. When the game starts the beauty is equal to zero. - The player that cannot move loses. Tweedledee and Tweedledum are legendary grand masters of combinatorial games, so they always play optimally. Playing optimally means that: - If there is at least one move that allows the players winn, then he will choose one of those moves according to the following priorities in order - Minimise the number of turns, he want to winn as quick as possible! - Maximise the beauty of the game. - If the player can't winn, then he will choose a move according to the following priorities in order - Maximise the number of turns, he want to last the longest possible!. - Maximise the beauty of the game. Ada doesn't want to wait till the end of the game. Help her finding the final beauty of the game. ###Input: - The first line of input contains an integer $T$, the number of test cases. - Each test case consist of a single containing one integer $N$, followed by $N$ space separated integers $B_1, B_2, ..., B_N$. ###Output: For each test case print the final beauty fo the game. ###Constraints - $3 \leq N \leq 10^5$ - $1 \leq B_i \leq 10^3$ - The sum of $N$ over all test cases does not exceed $5 \cdot 10^5$ ###Sample Input: ``` 1 5 1 2 3 4 5 ``` ###Sample Output: ``` 74 ```
|Tags||alei, cnmp2019, easy-medium, taran_1407|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.