Cod sursa(job #129467)

Utilizator undogSavu Victor Gabriel undog Data 29 ianuarie 2008 15:55:47
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<stdio.h>

int m,n;
int mat[20][20],cm[20];

int max;

void check(){
	int sum,lsum=0;
	for(int i=0;i<n;i++){
		sum=0;
		for(int j=0;j<m;j++)
			if(cm[j]==0)
				sum+=mat[i][j];
			else
				sum-=mat[i][j];
		if(sum<0)
			sum=-sum;
		lsum+=sum;
	}
	if(lsum>max)
		max=lsum;
}

void backtrack(int lvl){
	cm[lvl]=0;
	if(lvl>=m-1)
		check();
	else
		backtrack(lvl+1);
	cm[lvl]=1;
	if(lvl>=n-1)
		check();
	else
		backtrack(lvl+1);
}

int main(){
	
	freopen("flip.in","rt",stdin);
	freopen("flip.out","w+",stdout);
	
	scanf("%d%d",&m,&n);
	
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&mat[i][j]);
	
	backtrack(0);
	
	printf("%d",max);
	
	return 0;
}