Cod sursa(job #509414)
#include <iostream>
#include <fstream>
using namespace std;
/* algorithm is as follows */
/* 1. scan table horizontally, see if we can make a greater sum on any line, if yes, flip it
* 2. scan the table vertically, see if we can make a greater sum on any column, if yes, flip it
* 3. when no more permutations are possible we obtained the max sum */
/* checks wether or not to flip a col, and if so, flips it. */
int main()
{
int n, m;
ifstream in("flip.in");
ofstream out("flip.out");
in >> n >> m;
/* allocate multi-dimensional array */
int **table = new int*[n];
for(int i = 0; i < 5; i++)
table[i] = new int[m];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
in >> table[i][j];
}
int sumn = 0, sumf = 0; /* sum of current state and sum of flipped state */
int sum = 0, lastsum = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
lastsum += table[i][j];
}
while(true) /* loop is broken automatically when lastsum == sum */
{
/* HORIZONTAL FLIP */
for(int i = 0; i < n; i++) /* line id */
{
for(int j = 0; j < m; j++)
{
sumn += table[i][j];
sumf += (table[i][j] * -1);
}
if(sumn < sumf)
{
for(int j = 0; j < m; j++)
table[i][j] = (table[i][j] * -1);
// cout << "Flip line " << i + 1 << endl;
sumn = sumf;
}
sumn = sumf = 0; /* reset sums */
}
for(int j = 0; j < m; j++)
{
for(int i = 0; i < n; i++)
{
sumn += table[i][j];
sumf += (table[i][j] * -1);
}
if(sumn < sumf)
{
for(int i = 0; i < n; i++)
table[i][j] = (table[i][j] * -1);
// cout << "Flipping row " << j + 1 << endl;
}
sum += sumn;
sumn = sumf = 0;
}
if(lastsum == sum) /* no more possible moves */
{
out << sum;
break;
}
lastsum = sum;
sum = 0;
}
}