Cod sursa(job #1991404)

Utilizator hertzalauPOPESCU ION hertzalau Data 16 iunie 2017 17:47:33
Problema Jocul Flip Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#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];
int smax= -2147483647, 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);}
    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];
    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;
}