Cod sursa(job #477613)

Utilizator petroMilut Petronela petro Data 15 august 2010 15:36:25
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>
#include<stdlib.h>
FILE *f=fopen("flip.in","r");
FILE *g=fopen("flip.out","w");

#define M 17
long a[M][M];
int l[M],c[M],n,m;
long s=-2000000000;

void cit()
{
	int i,j;
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			fscanf(f,"%ld",&a[i][j]);
	fclose(f);
}

int sol()
{
	int i,j,su=0,sum=0;
	for(i=1;i<=n;++i)
	{
		su=0;
		for(j=1;j<=m;++j)
			su+=a[i][j]*l[i];
		if(su<=0) sum-=su;
		else sum+=su;
	}
	if(sum>s) s=sum;
}

void bkt(int k)
{
	if(k>n) sol();
	else {l[k]=1;
		  bkt(k+1);
		  l[k]=-1;
		  bkt(k+1);}
}

int sol2()
{
	int i,j,su=0,sum=0;
	for(i=1;i<=n;++i)
	{
		su=0;
		for(j=1;j<=m;++j)
			su+=a[i][j]*c[j];
		if(su<=0) sum-=su;
		else sum+=su;
	}
	if(sum>s) s=sum;
}

void bkt2(int k)
{
	if(k>m) sol2();
	else {c[k]=1;
		  bkt2(k+1);
		  c[k]=-1;
		  bkt2(k+1);}
}

int main()
{
	cit();
	bkt(1);
	//bkt2(1);
	fprintf(g,"%ld\n",s);
	fclose(g);
	return 0;
}