Cod sursa(job #234664)
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
int M, N;
ifstream in("flip.in");
in>>M>>N;
long *tabla = new long[M * N];
long *colSum = new long[max(M, N)];
for (int i = 0; i < max(M, N); i++)
colSum[i] = 0;
// if M > N transpose matrix
// we check 2^M line flips, so it should matter
if (M < N) {
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++) {
long val;
in >> val;
colSum[j] += val;
tabla[i * N + j] = 2 * val;
}
} else {
for (int j = 0; j < M; j++)
for (int i = 0; i < N; i++) {
long val;
in >> val;
colSum[j] += val;
tabla[i * M + j] = 2 * val;
}
int tmp = M;
M = N;
N = tmp;
}
in.close();
bool *flipLine = new bool[M], *flipCol = new bool[N];
for (int i = 0; i < M; i++)
flipLine[i] = false;
for (int i = 0; i < N; i++)
flipCol[i] = false;
// only to avoid compiler warning
long maxSum = LONG_MIN;
long crtSum;
do {
// add column sums (absolute value)
crtSum = 0;
for (int i = 0; i < N; i++) {
crtSum += abs(colSum[i]);
}
// compare crtSum with maxSum
if (crtSum > maxSum) {
maxSum = crtSum;
}
// increment flipLine binary number
int crtLine = M - 1;
bool transport = true;
while (crtLine >= 0 && transport) {
flipLine[crtLine] = !flipLine[crtLine];
if (flipLine[crtLine]) {
transport = false;
for (int j = 0; j < N; j++)
colSum[j] -= tabla[crtLine * N + j];
}
else {
for (int j = 0; j < N; j++)
colSum[j] += tabla[crtLine * N + j];
}
crtLine--;
}
if (crtLine < 0 && transport)
break;
} while (true);
ofstream out("flip.out");
out << maxSum << endl;
out.close();
return 0;
}