Pagini recente » Cod sursa (job #141938) | Cod sursa (job #798246) | Cod sursa (job #602224) | Cod sursa (job #262563) | Cod sursa (job #2046840)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int nrLines, nrColumns, element[20][20], sumLine[20], sumColumn[20], maxSum, sumHere;
vector < int > nrWhereFlip;
inline void flip(int opType, int nr) {
if (!opType) {
sumLine[nr] = 0;
for (int i = 1; i <= nrColumns; ++i)
sumHere -= 2 * element[nr][i],
sumColumn[i] -= 2 * element[nr][i],
element[nr][i] = -element[nr][i],
sumLine[nr] += element[nr][i];
return;
}
sumColumn[nr] = 0;
for (int i = 1; i <= nrLines; ++i)
sumHere -= 2 * element[i][nr],
sumLine[i] -= 2 * element[i][nr],
element[i][nr] = -element[i][nr],
sumColumn[nr] += element[i][nr];
}
inline void doForColumns() {
for (int i = 1; i <= nrColumns; ++i)
if (sumColumn[i] < 0) {
flip(1, i);
nrWhereFlip.push_back(i);
}
}
inline void undoForColumns() {
for (int i = 0; i < nrWhereFlip.size(); ++i)
flip(1, nrWhereFlip[i]);
nrWhereFlip.clear();
}
void backTrackLines(int nowLine) {
if (nowLine == nrLines) {
doForColumns();
maxSum = max(maxSum, sumHere);
undoForColumns();
flip(0, nowLine);
doForColumns();
maxSum = max(maxSum, sumHere);
undoForColumns();
flip(0, nowLine);
}
else {
backTrackLines(nowLine + 1);
flip(0, nowLine);
backTrackLines(nowLine + 1);
flip(0, nowLine);
}
}
int main()
{
fin >> nrLines >> nrColumns;
for (int i = 1; i <= nrLines; ++i) {
for (int j = 1; j <= nrColumns; ++j) {
fin >> element[i][j];
sumHere += element[i][j];
sumLine[i] += element[i][j];
sumColumn[j] += element[i][j];
}
}
backTrackLines(1);
fout << maxSum;
return 0;
}