Pagini recente » Cod sursa (job #109660) | Cod sursa (job #1209824) | Cod sursa (job #3246151) | Cod sursa (job #1264819) | Cod sursa (job #1280181)
#include <cstdio>
using namespace std;
// #define MAXS -99999999
int max_sum = -99999999;
int n, m;
int mat[20][20], sgn[20];
int getSum();
void backtrackSgn(int);
int main(int argc, char *argv[])
{
freopen("flip.in", "r", stdin);
freopen("flip.out", "w", stdout);
scanf("%d %d", &n, &m);
if (n >= m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &mat[i][j]);
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &mat[j][i]);
}
}
int aux = n;
n = m;
m = aux;
}
backtrackSgn(0);
printf("%d\n", max_sum);
return 0;
}
int getSum()
{
int ret = 0;
for (int i = 0; i < n; i++){
int s = 0;
for (int j = 0; j < m; ++j)
s += sgn[j] * mat[i][j];
if (s < 0)
s *= -1;
ret += s;
}
return ret;
}
void backtrackSgn(int poz)
{
if (poz < m) {
sgn[poz] = 1;
backtrackSgn(poz + 1);
sgn[poz] = -1;
backtrackSgn(poz + 1);
} else {
// int currentSum = getSum();
max_sum = getSum() > max_sum ? getSum() : max_sum;
}
}