Cod sursa(job #465198)

Utilizator ursu-valiJerdea Florin ursu-vali Data 23 iunie 2010 16:34:58
Problema Jocul Flip Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#define infile "flip.in"
#define outfile "flip.out"
#define nmax 20
#define inf ~(1<<31)
long a[nmax][nmax];
long n,m;
long smax=(-1)*inf;

long max(long a,long b)
{
	if(a>b) return a; return b;
}

void change(long p)
{
	long i;
	for(i=1;i<=m;i++)
		a[p][i]=-a[p][i];
}

void verif()
{
	long s=0;
	long i,j,k;
	for(i=1;i<=m;i++)
	{
		k=0;
		for(j=1;j<=n;j++)
			k+=a[j][i];
		s+=max(k,(-1)*k);
	}
	if(s>smax)
		smax=s;
}

void bk(long p)
{
	if(p>n)
		verif();
	else
	{
		bk(p+1);
		change(p);
		bk(p+1);
		change(p);
	}
}

void read()
{
	long i,j;
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%ld",&a[i][j]);
}

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

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	read();
	bk(1);
	print();
	fclose(stdin);
	fclose(stdout);
	return 0;
}