Pagini recente » Cod sursa (job #2671110) | Cod sursa (job #3183710) | Cod sursa (job #346515) | Cod sursa (job #1193823) | Cod sursa (job #2776478)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
void print(int v[])
{
for (int i = 1; v[i]; i++)
fout << v[i] << " ";
fout << "\n";
}
int mat[18][18], n, m, sum, ans, pr[18][18], S;
int v[36];
void backt(int pas)
{
if (pas == n + m + 1)
return ;
for (int i = v[pas - 1] + 1; i <= n + m; i++)
{
sum = S;
v[pas] = i;
for (int j = 1; v[j]; j++)
if (v[j] <= n)
for (int k = 1; k <= m; k++)
{
sum -= pr[v[j]][k];
pr[v[j]][k] *= -1;
sum += pr[v[j]][k];
}
else
for (int k = 1; k <= n; k++)
{
sum -= pr[k][v[j] - n];
pr[k][v[j] - n] *= -1;
sum += pr[k][v[j] - n];
}
ans = max(ans, sum);
memcpy(pr, mat, sizeof(mat));
backt(pas + 1);
}
v[pas] = 0;
}
int main()
{
int i, j;
fin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
fin >> mat[i][j];
S += mat[i][j];
pr[i][j] = mat[i][j];
}
ans = S;
backt(1);
fout << ans;
}