Pagini recente » Cod sursa (job #1995474) | Cod sursa (job #645517) | Cod sursa (job #1165703) | Cod sursa (job #2846226) | Cod sursa (job #2862788)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
#define MAXN 17
int mat[MAXN][MAXN], backupmat[MAXN][MAXN], sumcol[MAXN], newsumcol[MAXN];
int smatrix, newsmatrix;
void flip_line(int l, int m)
{
for(int c = 1; c <= m; c++)
{
newsumcol[c] -= 2 * mat[l][c];
newsmatrix -= 2 * mat[l][c];
mat[l][c] = -mat[l][c];
}
}
void rematrix(int n, int m)
{
for(int l = 1; l <= n; l++)
for(int c = 1; c <= m; c++)
mat[l][c] = backupmat[l][c];
}
int main()
{
int n, m, l, c;
fin >> n >> m;
for(l = 1; l <= n; l++)
for(c = 1; c <= m; c++)
{
fin >> mat[l][c];
sumcol[c] += mat[l][c];
newsumcol[c] = sumcol[c];
backupmat[l][c] = mat[l][c];
smatrix += mat[l][c];
}
newsmatrix = smatrix;
int i, ci, lin, maxsmatrix = 0;
for(i = 1; i <= (1 << n) - 1; i++)
{
ci = i;
lin = 0;
while(ci)
{
lin++;
if((ci & 1) == 1)
flip_line(lin, m);
ci >>= 1;
}
for(c = 1; c <= m; c++)
{
if(newsumcol[c] < 0)
newsmatrix -= 2 * newsumcol[c];
}
if(newsmatrix > maxsmatrix)
maxsmatrix = newsmatrix;
rematrix(n, m);
for(c = 1; c <= m; c++)
newsumcol[c] = sumcol[c];
newsmatrix = smatrix;
}
fout << maxsmatrix;
return 0;
}