Pagini recente » Cod sursa (job #2945704) | Cod sursa (job #1168600) | Cod sursa (job #3235145) | Cod sursa (job #1428429) | Cod sursa (job #2376332)
#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[2 * lung - 1];
int mat[lung][lung], cmat[lung][lung];
llong smax;
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)
sol[i] <= N ? 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 = sol[k - 1] + 1; i <= N + M; ++i)
{
sol[k] = i;
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;
}