Cod sursa(job #469580)

Utilizator SmarandaMaria Pandele Smaranda Data 8 iulie 2010 12:57:32
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
long a[17][17];
long sub[301];
int main()
{
	long n,m,i,j,poz=1,s=0,max,ns,t,sinit,sc,sl;
	unsigned char v,b;
	
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			scanf("%ld",&a[i][j]);
			s=s+a[i][j];
			if (a[i][j]<0)
				poz=0;
		}
	sinit=s;
	if (poz==1)
		printf("%ld\n",s);
	else
	{
		t=n;
		if (t<m)
			t=m;
		max=s;
		ns=(1<<t)-1;
		for (v=1;v<=ns;v++)
		{
			sub[0]=0;
			for (b=1;b<=t;b++)
				if (v&(1u<<b))
				{
					sub[++sub[0]]=b;
				}
			s=sinit;
			for (i=1;i<=sub[0];i++)
			{
				sc=s;
				sl=s;
				if (sub[i]<=n)
				{
					for (j=1;j<=m;j++)
					{
						sl=sl-a[sub[i]][j];
						sl=sl+(a[sub[i]][j]*-1);
					}
				}
				if (sub[i]<=m)
				{
					for (j=1;j<=n;j++)
					{
						sc=sc-a[j][sub[i]];
						sc=sc+(a[j][sub[i]]*(-1));
					}
				}
				if (sc>sl)
					s=sc;
				else
					s=sl;
			}
			if (s>max)
				max=s;
		}
		printf("%ld\n",max);
	}
	return 0;
}