Cod sursa(job #20012)

Utilizator szakiold name szaki Data 20 februarie 2007 16:18:23
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#define SIZE 32

int main()
{
	int n,m;
	int a[SIZE][SIZE];
	int s[SIZE]; //eredeti sorosszegek
	int i,j,k;
	int c,cmax;  //kombinacio
	int so, st;  //sorosszeg, teljes osszeg
	int smax;    //maximalis teljes osszeg

	freopen("flip.in","r", stdin);
	freopen("flip.out","w", stdout);
	scanf("%d %d", &n, &m);

	st=0;
	for (i=0;i<n;i++)
	{
		s[i]=0;
		for (j=0;j<m;j++)
		{
			scanf("%d", &a[i][j]);
			s[i]+=a[i][j];
			a[i][j]*=2;
		}
		st+=s[i];
	}
	smax=st;

	cmax=1<<m;
	for (c=0; c<cmax; c++)
	{
		st=0;
		for (i=0; i<n; i++)
		{
			so=s[i]; //eredetileg
			for(j=0, k=c; k>0; k>>=1, j++)
				if (k&1)
					so-=a[i][j]; //flip: x-2*x=-x
			if (so<0) st-=so;
			else st+=so;
		}
		if (st>smax) smax=st;
	}

	printf("%d",smax);
	return 0;
}