Cod sursa(job #316121)

Utilizator freak93Adrian Budau freak93 Data 18 mai 2009 15:50:30
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<cstdio>
#define maxn 16

using namespace std;

int a[maxn][maxn],x[maxn],i,j,n,m,k,b[maxn][maxn];

int smax,sm;

int lor()
{
	int sm=0,s;
	for(int i=1;i<=n;++i)
	{
		s=0;
		for(j=1;j<=m;++j)
			s+=b[i][j];
		if(s<0) sm-=s;
		else sm+=s;
	}
	
	return sm;
}

long long lver()
{
	int sm=0,s;
	for(int i=1;i<=m;++i)
	{
		s=0;
		for(j=1;j<=n;++j)
			s+=b[j][i];
		if(s<0) sm-=s;
		else sm+=s;
	}
	
	return sm;
}

void cpy()
{
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			b[i][j]=a[i][j];
}
int main()
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
	
	for(k=0;k<1<<m;++k)
	{
		cpy();
		for(i=0;i<m;++i)
			if(1<<i&k)
				for(j=1;j<=n;++j)
					b[j][i+1]=-b[j][i+1];
		sm=lor();
		if(sm>smax) smax=sm;
	}
	
	for(k=0;k<1<<n;++k)
	{
		cpy();
		for(i=0;i<n;++i)
			if(1<<i&k)
				for(j=1;j<=m;++j)
					b[i+1][j]=-b[i+1][j];
		sm=lver();
		if(sm>smax) smax=sm;
	}
	
	printf("%d\n",smax);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}