Cod sursa(job #705090)

Utilizator IronWingVlad Paunescu IronWing Data 3 martie 2012 00:46:39
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <cmath>
#include <climits>
#define MAX_EL 17

int main(){	
	freopen("flip.in","r", stdin);
	freopen("flip.out","w", stdout);
	int m, n, i, j, a[MAX_EL][MAX_EL], flip[MAX_EL], sumMax = INT_MIN, sumLin, sumCur, posN, bin, col;
	scanf("%d %d", &m, &n);
	for(i = 1; i<=m; ++i){
		for(j = 1; j<=n; ++j){
			scanf("%d", &a[i][j]);
		}
	}
	fclose(stdin);
	
	posN = 1<<n; // the number of possibilities of flipping n columns is 2^n
		for(j = 0; j < posN; ++j){
		/* generate all the possibilities for flipping columns */
		bin = j;		
		for(i = 1; i<=n; ++i){
			/* flip is the reverse binary representation of i */
			flip[i] = bin % 2;
			bin = bin / 2;		
		}
		/* compute the current sum for this flip combination of columns */
		sumCur = 0;
		for(i = 1; i <= m; ++i){
			/* for every line */
			sumLin = 0; // sum of this line is 0
			
			for (col = 1; col <= n; ++col){
				/* for every column of this line */
				if(flip[col] == 1){
					/* if the column was flipped, subtract (add with the opposite-flipped value) */
					sumLin -= a[i][col];
				}
				else{
					/* else, if the column was not flipped add with the normal value */
					sumLin += a[i][col];
				}
			}

			/* now, check the sum on this line */
			if(sumLin < 0){
				/* if the sum on this line is negative, flip the line (add with the oposite) */
				sumCur -= sumLin;
			}
			else {
				/* else, add with the sum of the line */
				sumCur += sumLin;
			}
		}
		if(sumCur > sumMax){
			/* if the sum of this possibility of flipped columns has a greater sum */
			sumMax = sumCur;
		}
	}

	printf("%d", sumMax);
	fclose(stdout);
	return 0;
}