Pagini recente » Cod sursa (job #377843) | Cod sursa (job #2504940) | Cod sursa (job #135987) | Rating Fornade Teodora (teo.01) | Cod sursa (job #1991413)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n, m, mp[17][17], md[17][17], v[17];
long long smax= -9223372036854775808, 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 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];
if(S>smax) smax=S;
}
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];
bk(1);
fout<<smax<<"\n";
return 0;
}