Pagini recente » Cod sursa (job #2473865) | Cod sursa (job #1562142) | Cod sursa (job #2158360) | Cod sursa (job #661112) | Cod sursa (job #2508728)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("flip.in");
ofstream fout ("flip.out");
//ifstream fin ("mine.in");
//ofstream fout ("mine.out");
int n, m, i, j, rows[26], collumns[26], matrix[26][26];
int valChange(int i, int j) {
return (-2)*(collumns[j] + rows[i] - matrix[i][j]);
}
void sign(int &a) { a *= (-1); }
int main() {
int totalSum = 0;
fin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++) {
fin >> matrix[i][j]; rows[i] += matrix[i][j];
totalSum += matrix[i][j]; collumns[j] += matrix[i][j];
}
// fout << totalSum << '\n';
int iMax, jMax, valMax, a;
bool keepgoing = 1;
while (keepgoing) {
iMax = 1, jMax = 1, valMax = valChange(iMax, jMax);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++) {
if (i == 1 && j == 1) continue;
a = valChange(i, j);
if (a > valMax)
{ valMax = a; iMax = i; jMax = j; }
}
if (valMax < 0)
keepgoing = 0;
else {
// fout << iMax << ' ' << jMax << ' ';
totalSum += valMax;
// fout << totalSum << '\n';
for (i = 1; i <= n; i++) {
sign(matrix[i][jMax]);
if (i != iMax)
rows[i] += 2*matrix[i][jMax];
}
for (i = 1; i <= m; i++) {
sign(matrix[iMax][i]);
if (i != jMax)
collumns[i] += 2*matrix[iMax][i];
}
sign(matrix[iMax][jMax]);
sign(rows[iMax]);
sign(collumns[jMax]);
// for (i = 1; i <= n; i++)
// fout << collumns[i] << ' ';
// fout << '\n';
}
}
fout << totalSum;// << '\n';
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++)
// fout << matrix[i][j] << ' ';
// fout << '\n';
// }
fin.close();
fout.close();
return 0;
}