Cod sursa(job #421502)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 21 martie 2010 14:22:18
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>
int N,M,smax,a[1<<5],m[1<<5][1<<5],b[1<<5][1<<5];
void copiaza()
{
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			b[i][j]=m[i][j];
}
void inmc(int j)
{
	for(int i=1;i<=N;i++)
		b[i][j]=-b[i][j];
}
void inml(int i)
{
	for(int j=1;j<=M;j++)
		b[i][j]=-b[i][j];
}
void rezolv()
{
	int s=0;
	int sum=0;
	copiaza();
	for(int i=1;i<=M;i++)
		if(a[i]==1)
			inmc(i);
	for(int i=1;i<=N;i++)
	{
		s=0;
		for(int j=1;j<=M;j++)
			s+=b[i][j];
		if(s<0)
			inml(i);
	}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			sum+=b[i][j];
	if(sum>smax)
		smax=sum;
}
void back(int l)
{
	if(l==M+1)
	{
		rezolv();
		return;
	}
	for(int i=0;i<=1;i++)
	{
		a[l]=i;
		back(l+1);
		a[l]=0;
	}
}
int main()
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			scanf("%d",&m[i][j]);
	back(1);
	printf("%d",smax);
	return 0;
}