Pagini recente » Cod sursa (job #404393) | Profil EugenStoica | Cod sursa (job #1419053) | Cod sursa (job #1676230) | Cod sursa (job #1743665)
#include <cstdio>
#include <vector>
using namespace std;
int n, m;
int mat[20][20];
vector<int> sol;
int maxSuma = 0;
void citire()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
scanf("%d", &mat[i][j]);
maxSuma += mat[i][j];
}
}
}
void calculareSuma()
{
for(int i = 0; i < sol.size(); i++)
{
if(sol[i] < n)
{
for(int j = 0; j < m; j++)
{
mat[sol[i]][j] *= -1;
}
}
else
{
for(int j = 0; j < n; j++)
{
mat[j][sol[i] - n] *= -1;
}
}
}
int suma = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
suma += mat[i][j];
}
}
if(suma > maxSuma)
{
maxSuma = suma;
}
for(int i = 0; i < sol.size(); i++)
{
if(sol[i] < n)
{
for(int j = 0; j < m; j++)
{
mat[sol[i]][j] *= -1;
}
}
else
{
for(int j = 0; j < n; j++)
{
mat[j][sol[i] - n] *= -1;
}
}
}
}
void backtracking()
{
long long limita = (long long)1 << (n + m);
for(long long k = 1; k < limita; k++)
{
sol.clear();
for(int i = 0; i <= 32; i++)
{
if((k & (1 << i)) != 0)
{
sol.push_back(i);
}
}
calculareSuma();
}
printf("%d", maxSuma);
}
int main()
{
freopen("flip.in", "r", stdin);
freopen("flip.out", "w", stdout);
citire();
backtracking();
return 0;
}