Cod sursa(job #167817)

Utilizator AndreyPAndrei Poenaru AndreyP Data 30 martie 2008 11:03:39
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>
int a[20][20],n,m,b[20][20];
int col[20],lin[20];
long long smax=0;
void calc(int k1,int k2)
{
	int i,j,x;
	long long s=0;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
			b[i][j]=a[i][j];
	}
	for(i=1; i<=k1; i++)
	{
		x=lin[i];
		for(j=1; j<=m; j++)
			b[x][j]=-b[x][j];
	}
	for(i=1; i<=k2; i++)
	{
		x=col[i];
		for(j=1; j<=n; j++)
			b[j][x]=-b[j][x];
	}
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
			s+=b[i][j];
	}
	if(s>smax)
		smax=s;
}
void back2(int k,int k2,int k1)
{
	if(k==k2+1)
	{
		calc(k1,k2);
		return;
	}
	int i;
	for(i=col[k-1]+1; i<=m; i++)
	{
		col[k]=i;
		back2(k+1,k2,k1);
	}
}
void coresp(int k1)
{
	int i;
	for(i=1; i<=m; i++)
		back2(1,i,k1);
}
void back1(int k,int k1)
{
	if(k==k1+1)
	{
		coresp(k1);
		return;
	}
	int i;
	for(i=lin[k-1]+1; i<=n; i++)
	{
		lin[k]=i;
		back1(k+1,k1);
	}
}
int main()
{
	int i,j;
	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]);
			smax+=a[i][j];
		}
	}
	for(i=1; i<=n; i++)
		back1(1,i);
	printf("%lld\n",smax);
	return 0;
}