Cod sursa(job #558170)

Utilizator raul1520Raul Andrei raul1520 Data 17 martie 2011 09:36:42
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
using namespace std;
int n,m,a[17][17],b[17][17],sc[17],sc2[17],sl[17],sl2[17],i,j,s,smax,q,t,r;
void Citeste()
{
	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]);
			b[i][j]=a[i][j];
			sc[j]=sc[j]+a[i][j];
		}
	}
}
void Scrie()
{
	printf("%d",smax);
}
int main()
{
	int k;
	Citeste();
	for(i=1;i<=m;i++)
	{
		sc2[i]=-sc[i];
		if(sc[i]<sc2[i])
		{
			sc[i]=sc2[i];
			for(j=1;j<=n;j++)
			{
				a[j][i]=-a[j][i];
			}
		}
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			sl[i]=sl[i]+a[i][j];
	s=0;
	for(i=1;i<=m;i++)
		s=s+sc[i];
	smax=s;
	q=(1<<n);
	for(i=1;i<q;i++)
	{
		t=i;
		r=0;
		for(k=1;k<=n;k++)
			sl2[k]=sl[k];
		while(t!=0)
		{
			r++;
			if(t%2==1)
			{			
				sl2[r]=-sl[r];
			}
			t=t/2;
		}
		s=0;
		for(j=1;j<=n;j++)
			s=s+sl2[j];
		if(s>smax)
		{
			smax=s;
		}
	}
	//+++++++++++++++++++++++++++++++++++
	for(i=1;i<=n;i++)
	{
		sl[i]=0;
		for(j=1;j<=m;j++)
		{	
			sc[j]=0;
			sl[i]=sl[i]+b[i][j];
		}
	}
	for(i=1;i<=n;i++)
	{
		sl2[i]=-sl[i];
		if(sl[i]<sl2[i])
		{
			sl[i]=sl2[i];
			for(j=1;j<=m;j++)
			{
				b[i][j]=-b[i][j];
			}
		}
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			sc[j]=sc[j]+b[i][j];
	s=0;
	for(i=1;i<=m;i++)
		s=s+sl[i];
	q=(i<<m);
	for(i=1;i<q;i++)
	{
		t=i;
		r=0;
		for(k=1;k<=n;k++)
			sc2[k]=sc[k];
		while(t!=0)
		{
			r++;
			if(t%2==1)
			{			
				sc2[r]=-sc[r];
			}
			t=t/2;
		}
		s=0;
		for(j=1;j<=n;j++)
			s=s+sc2[j];
		if(s>smax)
		{
			smax=s;
		}
	}
	//++++++++++++++++++++++++++++++
	Scrie();
	return 0;
}