Cod sursa(job #166132)

Utilizator luana_0105Fagarasan Luana luana_0105 Data 27 martie 2008 14:39:31
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include<string.h>

#define nmax 20 

int n,m, a[nmax][nmax], s[nmax];
int best;

void read()
{
     int i,j;
     freopen("flip.in","r",stdin);
     freopen("flip.out","w",stdout);
     scanf("%d%d", &n, &m);
     for(i=1; i<=n; ++i)
       for(j=1; j<=m; ++j)
         scanf("%d", &a[i][j]);
 
}

void solve()
{
     int i,j,k, sol;
     best=-100000000;
     for(i=0;i<1<<n; ++i)
     {
        for(j=1; j<=n; ++j)
         if((1<<(j-1))&i)
          for(k=1; k<=m;++k)
            a[j][k]=-a[j][k];
        memset(s, 0, sizeof(s));
        sol=0;
        for(k=1; k<=m; ++k)
          for(j=1; j<=n;++j)
            s[k]+=a[j][k];
        for(k=1; k<=m; ++k)
          if(s[k]<0)
            sol-=s[k];
          else
            sol+=s[k];
        if(sol> best)
          best=sol;
        for(j=1; j<=n; ++j)
         if((1<<(j-1))&i)
          for(k=1; k<=m;++k)
            a[j][k]=-a[j][k];
     }
}

int main()
{
    read();
    solve();
    printf("%d\n", best);
    return 0;
}