Pagini recente » Cod sursa (job #2978477) | Cod sursa (job #1909430) | Cod sursa (job #566807) | Cod sursa (job #2220231) | Cod sursa (job #3200846)
#include <iostream>
#include <fstream>
#include <set>
#include <cstring>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n, m, v[101], f[101], a[101][101], smax;
void flip(int k)
{
int i, j, stotal = 0;
for (i = 1; i <= k; i++)
{
for (j = 1; j <= n; j++)
a[v[i]][j] *= (-1);
}
for (j = 1; j <= m; j++)
{
int s = 0;
for (i = 1; i <= n; i++)
s += a[i][j];
if (s < 0)
s *= (-1);
stotal += s;
}
smax = max(smax, stotal);
for (i = 1; i <= k; i++)
{
for (j = 1; j <= n; j++)
a[v[i]][j] *= (-1);
}
}
bool valid(int k)
{
int i;
for (i = 1; i < k; i++)
if (v[i] == v[k])
return false;
if (k > 1 && v[k] <= v[k - 1])
return false;
return true;
}
void bkt(int k)
{
int i;
for (i = 1; i <= n; i++)
{
v[k] = i;
if (valid(k))
{
flip(k);
bkt(k + 1);
}
}
}
int main()
{
fin >> n >> m;
int i, j;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
fin >> a[i][j];
bkt(1);
fout << smax;
return 0;
}