Pagini recente » Cod sursa (job #2275465) | Cod sursa (job #2002601) | Cod sursa (job #2049170) | Cod sursa (job #39078) | Cod sursa (job #1514375)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M;
long long maxSum;
int mat[20][20], aux[20][20];
long long computeSum() {
long long Ans = 0;
for(register int i = 1; i <= N; ++ i)
for(register int j = 1; j <= M; ++ j)
Ans += aux[i][j];
return Ans;
}
void comuteCol(int col) {
for(register int i = 1; i <= N; ++ i)
aux[i][col] *= -1;
}
void comuteLine(int lin) {
for(register int i = 1; i <= M; ++ i)
aux[lin][i] *= -1;
}
void Combinations(int n, int k, int size = 0, int last = 0, int inComb = 0) {
if(size == k) {
for(register int i = 1; i <= n; ++ i)
if(inComb & (1 << i)) {
if(i > M) comuteLine(i - M);
else comuteCol(i);
//fprintf(stderr, "%d ", i);
}
//fprintf(stderr, "\n");
maxSum = max(maxSum, computeSum());
memcpy(aux, mat, sizeof(mat));
} else {
for(register int i = last + 1; i <= n; ++ i)
Combinations(n, k, size + 1, i, inComb xor (1 << i));
}
}
void backtracking() {
memcpy(aux, mat, sizeof(mat));
// for(register int i = 1; i <= N; ++ i, fprintf(stderr, "\n"))
// for(register int j = 1; j <= M; ++ j)
// fprintf(stderr, "%d ", aux[i][j]);
maxSum = computeSum();
for(register int i = 1; i <= N + M; ++ i)
Combinations(N + M, i);
}
int main(void) {
freopen("flip.in", "r", stdin);
freopen("flip.out", "w", stdout);
scanf("%d %d", &N, &M);
for(register int i = 1; i <= N; ++ i)
for(register int j = 1; j <= M; ++ j)
scanf("%d", &mat[i][j]);
backtracking();
printf("%lld\n", maxSum);
return 0;
}