Cod sursa(job #221361)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 16 noiembrie 2008 11:29:12
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>

int a[17][17],m,n,sp[17],sn[17],flip[17],si,smax,s[17];

void sol(){
int i,j,sc=0;
for(i=1;i<=n;++i)
	if(s[i]!=flip[i]){
		flip[i]=1-flip[i];
		for(j=1;j<=m;++j) {
			if(a[i][j]>=0) sp[j]-=a[i][j],sn[j]+=a[i][j];
			else sn[j]-=-a[i][j],sp[j]+=-a[i][j];
			a[i][j]=-a[i][j];
			}
		}

for(j=1;j<=m;++j)
	if(sp[j]>=sn[j]) sc+=sp[j]-sn[j];
	else  sc+=sn[j]-sp[j];
if(sc>smax) smax=sc;
}

void bkt(int k){
	if(k==n+1) sol();
	else{
		s[k]=-1;
		while(s[k]<1){
			s[k]++;
			bkt(k+1);
			}
		}
}

int main(){
int i,j;
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]);
		if(a[i][j]>=0) sp[j]+=a[i][j];
		else sn[j]+=-a[i][j];
		si+=a[i][j];
		}
bkt(1);

printf("%d",smax);
return 0;
}