Cod sursa(job #698313)

Utilizator Victor10Oltean Victor Victor10 Data 29 februarie 2012 13:22:44
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>

int cit[21][21], incol[21][21]; //cit- matricea citita; incol- matricea inmultita pe coloane

bool verif (int i, int j){
	if( 1<<j & i ) return 1;
	return 0;
}

int main(){
	
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	
	
	
	int n, m, i, i2, j2, j, colbit=0; //colbit = coloanele care le vom inmulti cu -1
	long long Smax=0, Scur;
	
	scanf("%d %d",&n,&m);
	for(i=1; i<=n; ++i) for(j=1; j<=m; ++j) scanf("%d",&cit[i][j]);
	
	//printf(" \n%d\n	",1<<m);
	for(; colbit<(1<<m); ++colbit){
		for(i=0; (1<<i)<=colbit*2; ++i){
			if(verif(colbit, i)){
				for(j=1; j<=n; ++j){
					incol[j][i+1]= cit[j][i+1] * (-1);
				}
			}
			else{
				for(j=1; j<=n; ++j)
					incol[j][m+i]=cit[j][m+i]; 
			}
		}
		
		for(i2=1; i2<=n; ++i2){
			Scur=0;
			for(j2=1; j2<=m; ++j2){
				Scur+=incol[i2][j2];
			}
			if(Scur<0){
				for(j2=1; j2<=m; ++j2){
					incol[i2][j2]*=(-1);
				}
			}
		}
		
		Scur=0;
		for(i2=1; i2<=n; ++i2)
			for(j2=1; j2<=m; ++j2)
				Scur+=incol[i2][j2];
		
		if(Scur>Smax){
			Smax=Scur;
		}
	}
	
	printf("%lld\n",Smax);
	return 0;
}