hackercupai/hackercup

1// Ethan Finds the Maximum Subarray Sum2// Solution by Jacob Plachta3 4#define DEBUG 05 6#include <algorithm>7#include <functional>8#include <numeric>9#include <iostream>10#include <iomanip>11#include <cstdio>12#include <cmath>13#include <complex>14#include <cstdlib>15#include <ctime>16#include <cstring>17#include <cassert>18#include <string>19#include <vector>20#include <list>21#include <map>22#include <set>23#include <deque>24#include <queue>25#include <stack>26#include <bitset>27#include <sstream>28using namespace std;29 30#define LL long long31#define LD long double32#define PR pair<int,int>33 34#define Fox(i,n) for (i=0; i<n; i++)35#define Fox1(i,n) for (i=1; i<=n; i++)36#define FoxI(i,a,b) for (i=a; i<=b; i++)37#define FoxR(i,n) for (i=(n)-1; i>=0; i--)38#define FoxR1(i,n) for (i=n; i>0; i--)39#define FoxRI(i,a,b) for (i=b; i>=a; i--)40#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)41#define Min(a,b) a=min(a,b)42#define Max(a,b) a=max(a,b)43#define Sz(s) int((s).size())44#define All(s) (s).begin(),(s).end()45#define Fill(s,v) memset(s,v,sizeof(s))46#define pb push_back47#define mp make_pair48#define x first49#define y second50 51template<typename T> T Abs(T x) { return(x<0 ? -x : x); }52template<typename T> T Sqr(T x) { return(x*x); }53string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }54 55const int INF = (int)1e9;56const LD EPS = 1e-12;57const LD PI = acos(-1.0);58 59#if DEBUG60#define GETCHAR getchar61#else62#define GETCHAR getchar_unlocked63#endif64 65bool Read(int &x)66{67	char c,r=0,n=0;68	x=0;69		for(;;)70		{71			c=GETCHAR();72				if ((c<0) && (!r))73					return(0);74				if ((c=='-') && (!r))75					n=1;76				else77				if ((c>='0') && (c<='9'))78					x=x*10+c-'0',r=1;79				else80				if (r)81					break;82		}83		if (n)84			x=-x;85	return(1);86}87 88int main()89{90		if (DEBUG)91			freopen("in.txt","r",stdin);92	// vars93	int T,t;94	int N,K;95	int i,m,w,s,c,ans;96	int A[100];97	// testcase loop98	Read(T);99		Fox1(t,T)100		{101			// input102			Read(N),Read(K);103			N=N*2-1;104			m=0;105				Fox(i,N)106					if (i%2==0)107						Read(A[i]),Max(m,A[i]);108				if (A[N-1]<0)109					N--;110			// consider each possible value w for Ethan's answer111			ans=0;112				FoxI(w,m,N*K+1)113				{114					// greedily fill in values115					s=c=0;116						FoxI(i,(A[0]<0 ? 1 : 0),N-1)117							if (i%2==0) // forced value?118							{119								s+=A[i];120									if (A[i]>=0)121										c+=A[i];122									else123										c=0;124							}125							else126							if (i==N-1) // last value?127							{128								if (c+K<=w) // fill with K if possible129									s+=K,c+=K;130							}131							else132							if (((A[i+1]<0) && (c+K<=w)) || ((A[i+1]>=0) && (c+K+A[i+1]<=w))) // can fill with K?133								s+=K,c+=K;134							else135								s--,c=0; // fill with -1 otherwise136					Max(ans,s-w);137				}138			// output139			printf("Case #%d: %d\n",t,ans);140		}141	return(0);142}