Problem: ethan_max_subarray (2018 round3)

In preparation for his final exam, Ethan is doing his fourth programming
assignment: finding the subarray with the maximum sum in an array of integers.

Given an array of **N** integers **A1..N**, Ethan's task is to find the
maximum sum of any (possibly empty) contiguous subarray of **A**. Ethan has
implemented an algorithm to solve this problem, described by the following
pseudocode:

  * 1\. Set **s** and **m** to both be equal to 0. 
  * 2\. Iterate _i_ upwards from 1 to **N**: 
  * 2a. If **Ai** ≥ 0, increment **s** by **Ai**, otherwise set **s** to be equal to 0. 
  * 2b. If **s** > **m**, set **m** to be equal to **s**. 
  * 3\. Output **m**. 

Is there any hope for Ethan? With exasperation, you set out in vain to teach
another lesson.

The professor of the class has once again left you with some half-written test
cases. You're given an initial array **B1..M**, such that the absolute value
of each element is at most **K**. You'd like to insert **M** \- 1 more
integers into the array, one between each pair of adjacent elements in the
original array, to construct a new array **A1..N** where **N** = 2**M** \- 1.
Each of the inserted elements must likewise have an absolute value of at most
**K**. You'll then feed the new array **A** into Ethan's algorithm. Your goal
is to maximize the absolute difference between the final array's correct
maximum subarray sum and the output of Ethan's algorithm.

### Input

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

### Output

For the _i_th test case, output a line containing "Case #_i_: " followed by
the maximum possible absolute difference between the correct maximum subarray
sum and the output of Ethan's algorithm.

### Constraints

1 ≤ **T** ≤ 60  
1 ≤ **M** ≤ 50  
1 ≤ **K** ≤ 50  
-**K** ≤ **Ai** ≤ **K**   

### Explanation of Sample

In the first case, **A** = [3], and both Ethan's answer and the correct answer
are equal to 3.

In the second case, **A** = [-3], and both Ethan's answer and the correct
answer are equal to 0.

In the third case, one value will be inserted into **B**, and you should
choose to insert -1 to yield **A** = [2, -1, 2]. This results in Ethan's
answer being 2 and the correct answer being 3, yielding an absolute answer
difference of 1.

In the fourth case, there are multiple choices of inserted elements which
result in an absolute answer difference of 3. For example, it's possible for
Ethan's answer equal to be made to equal 3 while the correct answer equals 6.



Sample input:
6
1 10
3
1 10
-3
2 2
2 2
5 3
-1 1 0 -2 -1
10 10
3 -10 -1 4 9 3 -6 1 6 -10
50 25
13 9 22 10 10 21 17 -8 7 15 14 10 -4 23 2 15 -3 18 17 9 -1 17 15 10 21 10 -4 14 17 1 -4 -3 23 -4 19 2 16 -1 9 21 -7 9 20 10 11 20 7 18 17 10


Sample output:
Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 3
Case #5: 51
Case #6: 1485



Code: // Ethan Finds the Maximum Subarray Sum
// 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);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N,K;
	int i,m,w,s,c,ans;
	int A[100];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(K);
			N=N*2-1;
			m=0;
				Fox(i,N)
					if (i%2==0)
						Read(A[i]),Max(m,A[i]);
				if (A[N-1]<0)
					N--;
			// consider each possible value w for Ethan's answer
			ans=0;
				FoxI(w,m,N*K+1)
				{
					// greedily fill in values
					s=c=0;
						FoxI(i,(A[0]<0 ? 1 : 0),N-1)
							if (i%2==0) // forced value?
							{
								s+=A[i];
									if (A[i]>=0)
										c+=A[i];
									else
										c=0;
							}
							else
							if (i==N-1) // last value?
							{
								if (c+K<=w) // fill with K if possible
									s+=K,c+=K;
							}
							else
							if (((A[i+1]<0) && (c+K<=w)) || ((A[i+1]>=0) && (c+K+A[i+1]<=w))) // can fill with K?
								s+=K,c+=K;
							else
								s--,c=0; // fill with -1 otherwise
					Max(ans,s-w);
				}
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}