# TEAMSEL: Getting wa

http://www.codechef.com/problems/TEAMSEL/

I have used Dynamic Programming.

#include<stdio.h>
#include<stdlib.h>

int max(int a, int b);

int main()
{
int numberOfTestCases;
scanf("%d", &numberOfTestCases);
int val;
long sum;
for(;numberOfTestCases>0;numberOfTestCases--)
{
int N;
scanf("%d", &N);
int i, j;
int Numbers[N];
sum = 0;
for(i=0;i<N;i++)
{
scanf("%d", &Numbers[i]);
sum = sum + Numbers[i];
}

int ** Array1;
int ** Array2;
val = 0;
int val0 = N/2;
int val1 = val0 + 1;
Array1 = (int **)malloc(sizeof(int *) * N);
Array2 = (int **)malloc(sizeof(int *) * N);
for(i=0;i<N;i++)
{
Array1[i] = (int *)calloc((sum/2) + 1, sizeof(int));
Array2[i] = (int *)calloc((sum/2) + 1, sizeof(int));
}
if(Numbers[N-1] < (sum/2))
{
Array1[N-1][Numbers[N-1]] = 1;
Array2[N-1][Numbers[N-1]] = 1;
}

for(i=N-2;i>=0;i--)
{
for(j=0; j<=(sum/2); j++)
{
if(j==Numbers[i])
{
Array1[i][j] = 1;
}
else
{
if( j-Numbers[i] >=0 && Array2[i+1][j-Numbers[i]] != 0)
{
Array1[i][j] = Array2[i+1][j-Numbers[i]] + 1;
}
}
Array2[i][j] = max( Array1[i][j], Array2[i+1][j]);

if((Array1[i][j] == val0 || Array1[i][j] == val1) && N%2 == 1 )
{
if(j > val)
val = j;
}
else if(Array1[i][j] == val0 && N%2 == 0 )
{
if(j > val)
val = j;
}
}
}
if(numberOfTestCases != 1)
printf("%d %ld\n\n", val, sum - val);
for(i=0;i<N;i++)
{
free(Array1[i]);
free(Array2[i]);
}
free(Array1);
free(Array2);
}
printf("%d %ld", val, sum - val);
return 0;
}

int max(int a, int b)
{
return a>b ? a:b;
}