Cod sursa(job #5520)

Utilizator figure0907Andrei Gonczi figure0907 Data 12 ianuarie 2007 22:11:44
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <string.h>

#define maxn 17

int n,m;
int st[maxn],fol[1];
int a[maxn][maxn];
long max;

void readdata()
{
	FILE *f = fopen("flip.in","rt");
	fscanf(f,"%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			fscanf(f,"%d",&a[i][j]);
		}
	}
	fclose(f);
}

void sol()
{
	int c[maxn][maxn];
	int i,j;
	for (i=1;i<=n;i++)
	{
		if (st[i])
		{
			for (j=1;j<=m;j++)
			{
				c[i][j] = -a[i][j];
			}
		}
			else
		{
			for (j=1;j<=m;j++)
			{
				c[i][j] = a[i][j];
			}
		}
	}
	long s,t=0;
	for (j=1;j<=m;j++)
	{
		s=0;
		for (i=1;i<=n;i++)
		{
			s+=c[i][j];
		}
		if (s<0)
		{
			t+=-s;
		}
			else t+=s;
	}
	if (t>max) max=t;
}

void back(int k)
{
	if (k>n)
	{
		sol();
	}
		else
	{
		for (int i=0;i<=1;i++)
		{
			if (fol[i]<=n)
			{
				fol[i]++;
				st[k]=i;
				back(k+1);
				fol[i]--;
			}
		}
	}
}

void solve()
{
   max = 0;
	memset(fol,0,sizeof(fol));
	back(1);
}

void writedata()
{
	FILE *f = fopen("flip.out","wt");
	fprintf(f,"%ld",max);
	fclose(f);
}

int main()
{
	readdata();
	solve();
	writedata();

	return 0;
}