Cod sursa(job #698479)

Utilizator luca.boieruBoieru Luca luca.boieru Data 29 februarie 2012 14:20:10
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

int a[25][25], b[25][25];

bool valid(int x, int i){
	if(x & (1 << i)) return 1;
	return 0;
}

int main(){
	
	freopen("flip.in", "r", stdin);
	freopen("flip.out", "w", stdout);
	
	int n, m; scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j) scanf("%d", &b[i][j]);
	
	long long maxi = -999999999;
	
	for(int x = 0 ; x < (1 << m); ++ x){
		
		for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j) a[i][j] = b[i][j];
		
		for(int i = 1, k = m; i < (1 << m); (i <<= 1), -- k){
			if(valid (x, i)){
				for(int j = 1; j <= n; ++ j){
					a[j][k] *= -1;
				}
			}
		}
		for(int i = 1; i <= n; ++ i){
			long long s = 0;
			for(int j = 1; j <= m; ++ j)
				s += a[i][j];
				
			if(s < 0)
				for(int j = 1; j <= m; ++ j)
					a[i][j] *= -1;
		}
		
		long long s = 0;
		for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j) s += a[i][j];
		if(s > maxi) maxi = s;
	}
	printf("%lld", maxi);
	return 0;
}