`1./* * FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10 * Problem: 10032 tug of war * * @author Martin Lambeck * @version 1.0, 31.10.2010 * * Method : dp * Status : Accepted * Runtime: 1.544 * */#include <stdio.h>#include <memory.h>#define WEIGHT_RANGE 90001#define OFFSET 45000bool first = true;typedef unsigned long long uint64;//if a[X] has the bit Y (starting at 0) set,//then there is a configuration where exactly Y people are in group 1, and the sum of their weights is X.//multiple bits can be setuint64 *a = new uint64[WEIGHT_RANGE];uint64 *b = new uint64[WEIGHT_RANGE];int weight[101]; //weight of the peoplevoid testcase(){	int pers, sum=0;//number of person, sum of weights	scanf("%d", &pers);	for (int i = 0; i < pers; i++)		scanf("%d", weight+i);	for (int i = 0; i < pers; i++)			sum += weight[i];	memset(a, (uint64) 0, WEIGHT_RANGE * sizeof(uint64)); //clear	a[OFFSET + weight[0]] = 2; //bit 1 (starting at 0)	a[OFFSET - weight[0]] = 1; //bit 0	uint64 *prev = b, *cur = a, *tmp;	for (int i = 1; i < pers; i++)	{		tmp = cur; //use only two arrays, but alternate them on each run		cur = prev; //cur is to be filled (clear before)		prev = tmp; //prev is the array of the previous person		int w = weight[i];		memset(cur, (uint64) 0, WEIGHT_RANGE * sizeof(uint64));		for (int j = 0; j < WEIGHT_RANGE; j++)		{			if (prev[j] > 0)			{				cur[j+w] |= prev[j] << 1; //add person i to group 1				cur[j-w] |= prev[j]; //add person i to group 2			}		}	}	int diff = -1; //difference of total weight between the two teams	uint64 p1 = pers/2; //half of the people must be in group 1	uint64 p2 = (pers+1)/2; //if the number of persons is odd...	uint64 pattern = ((uint64)1 << p1) | ((uint64)1 << p2); //bitmask	for (int i = 0; i <= OFFSET && diff < 0; i++)		if (((cur[OFFSET+i] | cur[OFFSET-i]) & pattern) > 0)			diff = i; //optimal solution	printf("%s%d %d\n", first ? "" : "\n", (sum-diff)/2, (sum+diff)/2);	first = false;}int main(){	int cases;	scanf("%d", &cases);	for (int i = 0; i < cases; i++)		testcase();	delete a;	delete b;	return 0;}`