Cod sursa(job #210033)

Utilizator ilincaSorescu Ilinca ilinca Data 26 septembrie 2008 09:43:22
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

#define pr (x) fprinf (strderr, "%ld\n", x)

#define MAX -300000000

int n, m, a [20] [20];
long smax = MAX, s [20];

void sume_col ()
{
	int i, j;
	for (j=1; j<=m; ++j)	
		for (i=1; i<=n; ++i)
			s [j]+=a [i] [j];
}	

void scan ()
{
	int i, j;
	scanf ("%d%d", &n, &m);
	for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j)
			scanf ("%d", &a [i] [j]);
}

void transform (int x, long s2 [])
{
	int i, j;
	for (i=1; i<=m; ++i)
		s2 [i]=s [i];
	for (i=0; i<n; ++i)
		if ((1<<i) & x)		
			for (j=1; j<=m; ++j)
				s2 [j]-=2*a [i+1] [j];
}

void calcul (long s2 [])
{
	int i;
	long s=0;
	for (i=1; i<=m; ++i)
	{
		if (s2 [i] > 0)
			s+=s2 [i];
		else
			s+=s2 [i]*(-1);
	}
	if (smax < s)
		smax=s;
	   	
}

void submultimi ()
{
	int i, ns;
	long s2 [20];
	ns=(1<<n)-1;
	for (i=0; i<=ns; ++i)
	{
		transform (i, s2);
		calcul (s2);
	}	
}	

void print ()
{
	printf ("%ld", smax);
}

int main ()
{
	freopen ("flip.in", "r", stdin);
	freopen ("flip.out", "w", stdout);
	scan ();
	sume_col ();
	submultimi ();
	print ();
	return 0;
}