Problem: finshakes (2018 round3)

You know what a finshake is, right? It's just like a handshake. Except
performed by fish rather than humans.

There are **N** pools of water in a row, numbered from 1 to **N** in order.
Pool _i_'s water level is at an elevation of **Hi** metres. There are **N** \-
1 equally-tall walls, one between each pair of adjacent pools, with the top of
each wall at an elevation of **W** metres. All of the water levels are lower
than the tops of the walls (in other words, **Hi** < **W** for each _i_).

There are also **M** fish throughout the pools. The _i_th fish initially lives
in pool **Pi**, and has a jumping height of **Ji** metres. It can jump over a
wall from any given pool **a** to an adjacent pool **b** (such that |**a** \-
**b**| = 1) if and only if **Ji** > **W** \- **Ha**. Multiple fish may live in
the same pool.

Each of the **M** fish will spend some time jumping over walls amongst the
pools, before each choosing a final pool to settle in. After all of the fish
have settled down, for each unique unordered pair of fish who have ended up in
the same pool as one another, they will give each other a finshake. Assuming
the fish all work together, what's the maximum number of finshakes which can
occur once they've all settled down in their chosen pools?

### Input

Input begins with an integer **T**, the number of rows of pools. For each row
of pools, there is first a line containing the space-separated integers **N**,
**M**, and **W**. Then follows a line containing the **N** space-separated
integers **H1** through **HN**. Then **M** lines follow, the _i_th of which
contains the space-separated integers **Pi** and **Ji**.

### Output

For the _i_th row of pools, output a line containing "Case #_i_: " followed by
the maximum number of finshakes which can occur.

### Constraints

1 ≤ **T** ≤ 50  
1 ≤ **N** ≤ 500  
1 ≤ **M** ≤ 50  
2 ≤ **W** ≤ 1,000,000  
1 ≤ **Hi** < **W**  
1 ≤ **Pi** ≤ **N**  
1 ≤ **Ji** ≤ 1,000,000  

### Explanation of Sample

In the first case, neither fish has a sufficient jumping height to jump over
the wall from its own pool to the other pool. As such, each fish must remain
isolated in its own pool, resulting in 0 finshakes being exchanged.

In the second case, the second fish has sufficient jumping strength to go back
and forth over the wall. It should choose to settle in the first pool. With
both fish ending up in the same pool, they'll exchange 1 finshake.

In the third case, the first fish is unable to leave the first pool. The
fourth fish could decide to choose to stay in the first pool as well, and give
the first fish a finshake. However, it's better for the last 3 fish to all
congregate in the second pool instead, as this will result in a total of 3
finshakes being exchanged amongst them.



Sample input:
5
2 2 10
5 5
1 5
2 5
2 2 10
5 5
1 4
2 6
3 4 5
4 2 3
1 1
3 3
2 3
1 7
10 12 10
7 2 5 1 3 7 9 4 7 3
7 9
4 10
3 8
7 7
9 8
2 9
10 8
7 8
10 7
3 10
1 7
10 10
30 25 100
41 33 48 3 15 88 32 4 11 99 24 55 94 85 88 96 48 36 87 9 92 32 79 61 26 17 99 24 74 57
12 53
29 30
22 91
25 17
1 49
16 77
27 93
3 60
27 97
24 80
13 94
7 85
19 26
22 77
30 46
1 65
7 62
30 97
5 50
21 95
20 48
6 69
3 62
19 56
10 96


Sample output:
Case #1: 0
Case #2: 1
Case #3: 3
Case #4: 39
Case #5: 85



Code: // Finshakes
// 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 MAXN 500
#define MAXM 51

int N,M,W;
int H[MAXN];
int L[MAXM],R[MAXM];
vector<int> ch[MAXM];
int dyn[MAXM][MAXM][MAXM][MAXM],tmp[MAXM][MAXM][MAXM];
// dyn[i][a][m][b] = max. finshakes in i's subtree, such that:
//   a = number of fish at left edge of i's interval
//   m = max. number of fish in any pool within i's interval
//   b = number of fish at right edge of i's interval

void rec(int i)
{
	int j,c,a,a2,b,b2,m,m2,m3,d,d2,d3;
	bool o,e1,e2;
	// iterate over children
	dyn[i][0][0][0]=0;
		Fox(j,Sz(ch[i]))
		{
			// recurse to child
			rec(c=ch[i][j]);
				if (!j)
				{
					memcpy(dyn[i],dyn[c],sizeof(dyn[i]));
					continue;
				}
			// does this child overlap with the previous child?
			o=R[ch[i][j-1]]==L[c];
			// incorporate child into DP values
			Fill(tmp,-1);
				Fox(a,M+1)
					Fox(m,M+1)
						Fox(b,M+1)
							if ((d=dyn[i][a][m][b])>=0)
								Fox(a2,M+1)
									Fox(m2,M+1)
										Fox(b2,M+1)
											if ((d2=dyn[c][a2][m2][b2])>=0)
											{
												m3=max(m,m2);
												d3=d+d2;
													if (o)
													{
														Max(m3,b+a2);
														d3+=b*a2;
													}
												Max(tmp[a][m3][b2],d3);
											}
			memcpy(dyn[i],tmp,sizeof(dyn[i]));
		}
	// do the children extend to this interval's edges?
		if (Sz(ch[i]))
		{
			e1=L[ch[i][0]]==L[i];
			e2=R[ch[i][Sz(ch[i])-1]]==R[i];
			Fill(tmp,-1);
				Fox(a,M+1)
					Fox(m,M+1)
						Fox(b,M+1)
							Max(tmp[e1 ? a : 0][m][e2 ? b : 0],dyn[i][a][m][b]);
			memcpy(dyn[i],tmp,sizeof(dyn[i]));
		}
	// incorporate this fish
		if (i==M)
			return;
	Fill(tmp,-1);
		Fox(a,M+1)
			Fox(m,M+1)
				Fox(b,M+1)
					if ((d=dyn[i][a][m][b])>=0)
						if (L[i]==R[i])
						{
							// add onto only pool in interval
							Max(tmp[a+1][m+1][b+1],d+m);
						}
						else
						{
							// add onto left
							Max(tmp[a+1][max(m,a+1)][b],d+a);
							// add onto max
							Max(tmp[a][m+1][b],d+m);
							// add onto right
							Max(tmp[a][max(m,b+1)][b+1],d+b);
						}
	memcpy(dyn[i],tmp,sizeof(dyn[i]));
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i,j,p,a,m,b,ans;
	PR F[MAXM];
	set< pair<PR,int> > S;
	set< pair<PR,int> >::iterator I,J;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input, and compute fish intervals
			Read(N),Read(M),Read(W);
				Fox(i,N)
					Read(H[i]),H[i]=W-H[i];
				Fox(i,M)
				{
					Read(p),Read(j),p--;
					a=b=p;
						while ((a>0) && (H[a]<j))
							a--;
					L[i]=a;
						while ((b<N-1) && (H[b]<j))
							b++;
					R[i]=b;
				}
			// sort fish by interval sizes
				Fox(i,M)
					F[i]=mp(R[i]-L[i],i);
			sort(F,F+M);
			// form tree out of fish
				Fox(i,M+1)
					ch[i].clear();
			S.clear();
				Fox(i,M)
				{
					j=F[i].y;
					I=S.lower_bound(mp(mp(L[j],0),0));
						while ((I!=S.end()) && (I->x.y<=R[j]))
						{
							ch[j].pb(I->y);
							J=I,I++;
							S.erase(J);
						}
					S.insert(mp(mp(L[j],R[j]),j));
				}
				Foxen(I,S)
					ch[M].pb(I->y);
			// DP
			Fill(dyn,-1);
			rec(M);
			// get answer
			ans=0;
				Fox(a,M+1)
					Fox(m,M+1)
						Fox(b,M+1)
							Max(ans,dyn[M][a][m][b]);
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}