Cod sursa(job #579095)

Utilizator popacamilpopa camil popacamil Data 11 aprilie 2011 20:50:29
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<cstdio>
using namespace std;
long long int c,lin,col,n,m,k,a[17][17],v[17][17],sc,i,j,s,smax,exp,aux,d,e,f,g;
void flip(long long int k){
	for(c=1;c<=m;++c){
		a[k][c]=-a[k][c];
	}
}
long long int sum(long long int col){
	for(c=1;c<=n;++c){
		sc+=a[c][col];
	}
	return sc;
}
void colflip(){
	for(col=1;col<=m;++col){
		if(sum(col)<0){
			for(lin=1;lin<=n;++lin){
				a[lin][col]=-a[lin][col];
			}
		}
	}
	for(d=1;d<=n;++d){
		for(e=1;e<=m;++e){
			s+=a[d][e];
		}
	}
	if(smax<s){
		smax=s;
	}
}
int main(){
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j){
			scanf("%lld",&v[i][j]);
			a[i][j]=v[i][j];
			smax+=v[i][j];
		}
	}exp=1;
	for(i=1;i<=n;++i){
		exp*=2;
	}
	exp-=1;
	for(i=1;i<=exp;++i){
		aux=i;
		k=1;
		while(aux!=0){
			if(aux%2==1){
				flip(k);
			}
			aux/=2;
			++k;
		}
		colflip();
		for(f=1;f<=n;++f){
			for(g=1;g<=m;++g){
				a[f][g]=v[f][g];
			}
		}
	}
	printf("%lld",smax);
	return 0;
}