hackercupai/hackercup

1What day is it today? Wasn't there something you were supposed to remember?2Eh, it was probably nothing...3 4...5 6Wait! Oh no! It's your anniversary today! And you don't have a gift for your7spouse!8 9Only one thing can save you now: online shopping. Logging onto your favourite10shopping site, the top automated suggestion looks perfect (or at least11passable) — a graph. Your spouse probably loves graphs, right? More12importantly, it can be delivered directly to your house within half an hour.13 14The graph comes with **N** nodes, the _i_th of which is labelled with a non-15zero integer **Li**. Unfortunately, no edges are included by default — you16have to pay extra for those. You'd better purchase one or more edges so that17it looks like you put extensive thought into your gift. Purchasing an18undirected edge between two different nodes _i_ and _j_ costs **Li** * **Lj**19dollars (note that this cost may be negative, in which case you actually20receive money for "purchasing" that edge). You won't purchase more than one21edge between any unordered pair of nodes, and you won't purchase any self-22loops (edges connecting a node directly to itself).23 24In order to make the graph appealing to your spouse, you've decided that it25should have the following two properties:26 27  1. Each node should be adjacent to at least one other node. 28  2. Each node with a positive label should be adjacent to at most one node with a negative label. 29 30Any such graph should make a fine gift, so... you might as well go with the31cheapest option, right? You'd like to determine the minimum possible total32cost of edges to purchase which result in a graph with both properties33described above. Note that this total "cost" may be negative.34 35### Input36 37Input begins with an integer **T**, the number of test cases. For each test38case, there is first a line containing the integer **N**. Then one more line39follows containing the **N** space-separated integers **L1** through **LN**.40 41### Output42 43For the _i_th test case, output a line containing "Case #_i_: " followed by44the minimum cost (in dollars) required to complete the graph gift.45 46### Constraints47 481 ≤ **T** ≤ 40  492 ≤ **N** ≤ 30,000  50-10,000,000 ≤ **Li** ≤ 10,000,000   51**Li** ≠ 0   52 53### Explanation of Sample54 55In the first case, you should purchase an edge between the two nodes for a56cost of (-1)*(-1) = 1.57 58In the second case, you should purchase an edge from the third node to each of59the other nodes, for a cost of (-3)*(-1) + (-3)*2 + (-3)*4 = -15.60 61