Pagini recente » Cod sursa (job #1391472) | Cod sursa (job #2099945) | Cod sursa (job #2780596) | Cod sursa (job #850934) | Cod sursa (job #2376222)
#include <bits/stdc++.h>
#define lung 17
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
typedef unsigned short ushort;
typedef long long llong;
ushort N, M, sol[lung << 1 + 1];
int mat[lung][lung], cmat[lung][lung];
llong smax;
bool line(ushort val)
{
return val <= N;
}
bool ebun(ushort k)
{
if(k == 1)
return true;
if(line(sol[k]) != line(sol[k - 1]))
return true;
return sol[k] > sol[k - 1];
}
void comutare_linie(ushort l)
{
for(ushort c = 1; c <= M;)
mat[l][c++] *= -1;
}
void comutare_coloana(ushort c)
{
for(ushort l = 1; l <= N;)
mat[l++][c] *= -1;
}
llong suma(ushort k)
{
for(ushort i = 1; i <= N; ++i)
for(ushort j = 1; j <= M;)
cmat[i][j] = mat[i][j++];
for(ushort i = 1; i <= k; ++i)
line(sol[i]) ? comutare_linie(sol[i]) : comutare_coloana(sol[i] - N);
llong s = 0;
for(ushort i = 1; i <= N; ++i)
for(ushort j = 1; j <= M;)
s += cmat[i][j++];
return s;
}
void back(ushort k)
{
for(ushort i = 1; i <= N + M; ++i)
{
sol[k] = i;
if(ebun(k))
{
smax = max(smax, suma(k));
if(k < N + M)
back(k + 1);
}
}
}
int main()
{
in >> N >> M;
for(ushort i = 1; i <= N; ++i)
for(ushort j = 1; j <= M;)
{
in >> mat[i][j];
smax += mat[i][j++];
}
back(1);
out << smax;
return 0;
}