Problem: graph_gift (2018 round3)

What day is it today? Wasn't there something you were supposed to remember?
Eh, it was probably nothing...

...

Wait! Oh no! It's your anniversary today! And you don't have a gift for your
spouse!

Only one thing can save you now: online shopping. Logging onto your favourite
shopping site, the top automated suggestion looks perfect (or at least
passable) — a graph. Your spouse probably loves graphs, right? More
importantly, it can be delivered directly to your house within half an hour.

The graph comes with **N** nodes, the _i_th of which is labelled with a non-
zero integer **Li**. Unfortunately, no edges are included by default — you
have to pay extra for those. You'd better purchase one or more edges so that
it looks like you put extensive thought into your gift. Purchasing an
undirected edge between two different nodes _i_ and _j_ costs **Li** * **Lj**
dollars (note that this cost may be negative, in which case you actually
receive money for "purchasing" that edge). You won't purchase more than one
edge between any unordered pair of nodes, and you won't purchase any self-
loops (edges connecting a node directly to itself).

In order to make the graph appealing to your spouse, you've decided that it
should have the following two properties:

  1. Each node should be adjacent to at least one other node. 
  2. Each node with a positive label should be adjacent to at most one node with a negative label. 

Any such graph should make a fine gift, so... you might as well go with the
cheapest option, right? You'd like to determine the minimum possible total
cost of edges to purchase which result in a graph with both properties
described above. Note that this total "cost" may be negative.

### Input

Input begins with an integer **T**, the number of test cases. For each test
case, there is first a line containing the integer **N**. Then one more line
follows containing the **N** space-separated integers **L1** through **LN**.

### Output

For the _i_th test case, output a line containing "Case #_i_: " followed by
the minimum cost (in dollars) required to complete the graph gift.

### Constraints

1 ≤ **T** ≤ 40  
2 ≤ **N** ≤ 30,000  
-10,000,000 ≤ **Li** ≤ 10,000,000   
**Li** ≠ 0   

### Explanation of Sample

In the first case, you should purchase an edge between the two nodes for a
cost of (-1)*(-1) = 1.

In the second case, you should purchase an edge from the third node to each of
the other nodes, for a cost of (-3)*(-1) + (-3)*2 + (-3)*4 = -15.



Sample input:
5
2
-1 -1
4
-1 2 -3 4
8
9 4 11 5 7 9 12 3
20
-49 -23 -56 -90 21 -66 -12 -32 -28 -26 -85 -45 -9 -63 -29 1 5 -48 -63 -54
30
-109 -83 -16 -50 19 -26 -72 8 12 -86 -45 -5 -69 -123 11 -59 45 -8 -123 -114 41 -146 -48 3 -58 32 -129 -34 -32 -55


Sample output:
Case #1: 1
Case #2: -15
Case #3: 164
Case #4: 2332
Case #5: -20042



Code: // Graph Gift
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 30003

int NA,NB;
LL A[LIM],B[LIM];
LL SB[LIM];
LL mem3[LIM];

// cost for cross-pairing B values such that ny = n-y
LL Comp3(int ny)
{
		if (mem3[ny])
			return(mem3[ny]);
	int i;
	LL ans=0;
		Fox(i,(ny-1)/2)
			ans+=B[NB-i-2]*B[NB-ny+i];
	return(mem3[ny]=ans);
}

// min. cost for connecting last B values
LL Comp2(int n)
{
		if (!n)
			return(0);
		if ((n==1) && (NB>=2))
			return(B[NB-1]*B[NB-2]);
	int y;
	LL cur,ans=(LL)6e18;
	// pair first y values with the last value
		Fox1(y,n-1)
		{
				if ((n-y-1)%2)
					continue;
			cur=B[NB-1]*(SB[NB-n+y]-SB[NB-n]);
			// cross-pair the remaining n-y-1 values
			cur+=Comp3(n-y);
			Min(ans,cur);
		}
	return(ans);
}

// min. cost with last x A values paired with different B values
LL Comp1(int x)
{
	int i;
	LL ans=0;
		Fox(i,NA-x)
			ans-=B[0]*A[i];
		Fox(i,x)
			ans-=B[i+1]*A[NA-x+i];
	ans+=Comp2(NB-x-1);
	return(ans);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N;
	int i,x;
	LL ans,v;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
			NA=NB=0;
				while (N--)
				{
					Read(x);
						if (x>0)
							A[NA++]=x;
						else
							B[NB++]=-x;
				}
			// sort each list in non-increasing order
			sort(A,A+NA);
			sort(B,B+NB);
			reverse(A,A+NA);
			reverse(B,B+NB);
			// precompute prefix sums
				Fox(i,NB)
					SB[i+1]=SB[i]+B[i];
			// special case: all positive/negative?
			Fill(mem3,0);
				if ((!NA) || (!NB))
				{
						if (!NB)
						{
							NB=NA;
							memcpy(B,A,sizeof(A));
								Fox(i,NB)
									SB[i+1]=SB[i]+B[i];
						}
					ans=Comp2(NB);
				}
				else
				{
					// try all parameters
					ans=(LL)6e18;
						Fox(x,min(NA,NB))
							Min(ans,Comp1(x));
				}
			// output
			printf("Case #%d: %lld\n",t,ans);
		}
	return(0);
}