Cod sursa(job #358755)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 24 octombrie 2009 13:39:33
Problema Jocul Flip Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>
#define infile "flip.in"
#define outfile "flip.out"
#define nmax 21
#define inf ~(1<<31)
int a[nmax][nmax]; //matricea cu numere
int n,m; //numarul de linii, respectiv coloane
int smax=(-1)*inf; //suma maxima ce se poate obtine

inline int max(int a, int b)
{
	if(a>b) return a; return b;
}

inline void change(int p)
{ //inmultim cu (-1) valorile de pe linia p
	int i;
	for(i=1;i<=m;i++)
		a[p][i]*=(-1);
}

inline void verif()
{
	int s=0; //aici vom calcula suma
	int i,j,k;
	
	for(i=1;i<=m;i++) //luam fiecare coloana in parte
	{
		k=0; //aici vom calcula suma coloanei
		for(j=1;j<=n;j++) //toate poitiile de pe coloana
			k+=a[j][i]; //adaugam la suma
		s+=max(k,(-1)*k); //adaugam la suma, maximul dintre normal, si dintre schimbat
	}
	
	if(s>smax) smax=s; //daca am obtinut o suma mai mare
}

void read()
{
	int i,j;
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
}

void bk(int p)
{
	if(p>n) //daca am facut toate pozitiile
		verif(); //vedem daca putem obtine suma mai mare
	else
	{
		bk(p+1); //rezolvam mai departe cand nu schimbam linia p
		change(p); //schimbam linia p
		bk(p+1); //rezolvam mai departe cu linia p schimbata
		change(p); //refacem linia p
	}
}

void write()
{
	printf("%d\n",smax);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	bk(1);
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}