Pagini recente » Cod sursa (job #918558) | Cod sursa (job #526037) | Cod sursa (job #1565841) | Cod sursa (job #1828699) | Cod sursa (job #2282083)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
int M[20][20];
int c[20][20];
int v[20];
bool marcat[20];
int n, m;
int mx;
void markcol(int col)
{
for(int i = 1; i <= n; i++)
M[i][col] *= (-1);
}
int aflare_maxim()
{
int maxim = 0;
for(int i = 1; i <= n; i++)
{
int s = 0;
for(int j = 1; j <= m; j++)
s += M[i][j];
if(s < 0)
maxim = maxim + s * (-1);
else
maxim += s;
}
return maxim;
}
void _back_(int poz)
{
if(poz > 0)
{
for(int i = 1; i <= poz; i++)
if(v[i])
markcol(i);
mx = max(mx, aflare_maxim());
for(int i = 1; i <= poz; i++)
markcol(v[i]);
}
if(poz == n + 1)
return;
for(int i = v[poz - 1] + 1; i <= n; i++)
{
v[poz] = i;
_back_(poz + 1);
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
in >> M[i][j];
_back_(1);
out << mx;
return 0;
}