Pagini recente » Cod sursa (job #987764) | Cod sursa (job #2682380) | Cod sursa (job #1016043) | Cod sursa (job #3239643) | Cod sursa (job #1746870)
#include <cstdio>
using namespace std;
const int DIM = 16;
int a[DIM + 5][DIM + 5], aux[DIM + 5][DIM + 5];
void copy(int n, int m){
int i, j;
for (i = 1; i <= n; i ++)
for (j = 1; j <= m; j ++)
aux[i][j] = a[i][j];
}
int solve(int n, int m, int s){
int i, j;
long long sum;
for (j = 1; j <= m; j ++){
sum = s;
for (i = 1; i <= n; i ++)
sum -= 2 * aux[i][j];
if (sum > s){
s = sum;
for (i = 1; i <= n; i ++)
aux[i][j] = -aux[i][j];
}
}
return s;
}
int main(){
freopen("flip.in", "r", stdin);
freopen("flip.out", "w", stdout);
int n, m, i, j, k, ns, s = 0, sum, max = -256000000;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i ++)
for (j = 1; j <= m; j ++){
scanf("%d", &a[i][j]);
s += a[i][j];
}
ns = (1 << n) - 1;
for (i = 1; i <= ns; i ++){
copy(n, m);
sum = s;
for (j = 0; j < n; j ++)
if ((1 << j) & i)
for (k = 1; k <= m; k ++){
sum -= 2 * aux[j + 1][k];
aux[j + 1][k] = -aux[j + 1][k];
}
sum = solve(n, m, sum);
max = max > sum ? max:sum;
}
printf("%d\n", max);
return 0;
}