Pagini recente » Cod sursa (job #1819616) | Cod sursa (job #1963099) | Cod sursa (job #1804575) | Cod sursa (job #1341637) | Cod sursa (job #1991402)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n, m, v[17];
int mp[17][17], md[17][17];
long long smax=-3200000*10000, ct;
void flip2(int I)
{for(int j=1; j<=m; j++) mp[I][j]=mp[I][j]*(-1);}
void flip(int X){for(int I=1; I<=n; I++) mp[I][X]=mp[I][X]*(-1); }
void me(int nc)
{ int i; for(i=1; i<=nc; i++) flip(v[i]);
for(i=1; i<=m; i++){
int sum=0; for(int j=1; j<=n; j++) sum+=mp[i][j];
if(sum<0) flip2(i);}
long long int S=0;
for(i=1; i<=n; i++) for(int j=1; j<=m; j++) S+=mp[i][j], mp[i][j]=md[i][j];
smax=max(S, smax);
}
void generare_solutii(int nc, int p)
{
for(int pp=v[p-1]+1; pp<=m-nc+p; pp++) {v[p]=pp; if(p==nc) me(nc); else generare_solutii(nc, p+1);}
}
void bk(int nc)
{ if(nc<=m){
generare_solutii(nc, 1); for(int i=1; i<=17; i++) v[i]=0;
bk(nc+1); }
}
int main()
{
int i, j;
fin>>n>>m; for(i=1; i<=n; i++) for(j=1; j<=m; j++) fin>>mp[i][j];
for(i=1; i<=n; i++) for(j=1; j<=m; j++) md[i][j]=mp[i][j];
long long int S=0;
for(i=1; i<=n; i++) for(int j=1; j<=m; j++) S+=mp[i][j], mp[i][j]=md[i][j];
smax=max(S, smax);
bk(1);
fout<<smax<<"\n";
return 0;
}