Pagini recente » Profil UPB_Darius_Rares_Silviu | Monitorul de evaluare | Statistici Dobocan Sergiu (DobocanSergiu) | Cod sursa (job #2425643) | Cod sursa (job #2801040)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n, m;
int v[19], col[19], mat[19][19], sum, ans;
bool f[19];
void afis()
{
for (int i = 1; i <= n; i++)
cout << v[i] << " ";
}
void flip(int i)
{
for (int j = 1; j <= m; j++)
{
mat[i][j] *= -1;
sum += 2 * mat[i][j];
}
}
void backt(int pas)
{
if (pas == n + 1)
return ;
for (int i = v[pas - 1] + 1; i <= n; i++)
{
if (f[i])
continue;
v[pas] = i;
f[i] = 1;
for (int i = 1; v[i]; i++)
flip(v[i]);
ans = max(ans, sum);
/*afis();
cout << " " << sum << "\n";*/
for (int i = 1; v[i]; i++)
flip(v[i]);
backt(pas + 1);
v[pas] = 0;
f[i] = 0;
}
}
int main()
{
fin >> n >> m;
int i, j;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
fin >> mat[i][j];
sum += mat[i][j];
col[j] += mat[i][j];
}
ans = sum;
backt(1);
for (j = 1; j <= m; j++)
//if (col[j] <= 0)
{
int aux = sum;
for (i = 1; i <= n; ++i)
{
mat[i][j] *= -1;
sum += 2 * mat[i][j];
}
ans = max(ans, sum);
backt(1);
for (i = 1; i <= n; ++i)
mat[i][j] *= -1;
sum = aux;
}
fout << ans;
}