Pagini recente » Cod sursa (job #1101966) | Cod sursa (job #1595071) | Cod sursa (job #2742652) | Cod sursa (job #2165536) | Cod sursa (job #705090)
Cod sursa(job #705090)
#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;
}