Pagini recente » Cod sursa (job #666066) | Cod sursa (job #2149362) | Cod sursa (job #1213197) | Cod sursa (job #1730466) | Cod sursa (job #1743695)
#include <cstdio>
#include <vector>
using namespace std;
int n, m;
int mat[20][20];
int sumeLinie[20];
int sumeColoane[20];
vector<int> sol;
int solx[20];
int maxSuma = 0;
int sumaInitiala;
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]);
sumeLinie[i] += mat[i][j];
sumeColoane[j] += mat[i][j];
maxSuma += mat[i][j];
sumaInitiala += mat[i][j];
}
}
}
void calculareSuma()
{
int suma = sumaInitiala;
for(int i = 0; i < 20; i++)
{
solx[i] = 0;
}
for(int i = 0; i < sol.size(); i++)
{
suma -= 2 * sumeLinie[sol[i]];
solx[sol[i]] = 1;
}
int tmp1;
for(int i = 0; i < m; i++)
{
tmp1 = 0;
for(int j = 0; j < n; j++)
{
if(solx[j] == 0)
{
tmp1 += mat[j][i];
}
else
{
tmp1 -= mat[j][i];
}
}
if(tmp1 < 0)
{
suma += 2 * (-tmp1);
}
}
if(suma > maxSuma)
{
maxSuma = suma;
}
}
void backtracking()
{
long long limita = (long long)1 << (m);
for(long long k = 1; k < limita; k++)
{
sol.clear();
for(int i = 0; i <= 16; 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;
}