Cod sursa(job #316140)

Utilizator zaNNyEnacache Razvan Daniel zaNNy Data 18 mai 2009 16:41:00
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<cstdio>   
#define maxn 18   
  
using namespace std;   
  
int a[maxn][maxn],x[maxn],i,j,n,m,k,b[maxn][maxn];   
  
int smax,sm;   
  
int lor()   
{   
    int sm=0,s;   
    for(int i=1;i<=n;++i)   
    {   
        s=0;   
        for(j=1;j<=m;++j)   
            s+=b[i][j];   
        if(s<0) sm-=s;   
        else sm+=s;   
    }   
       
    return sm;   
}   
  
long long lver()   
{   
    int sm=0,s;   
    for(int i=1;i<=m;++i)   
    {   
        s=0;   
        for(j=1;j<=n;++j)   
            s+=b[j][i];   
        if(s<0) sm-=s;   
        else sm+=s;   
    }   
       
    return sm;   
}   
  
void cpy()   
{   
    for(int i=1;i<=n;++i)   
        for(int j=1;j<=m;++j)   
            b[i][j]=a[i][j];   
}   
int main()   
{   
    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]);   
       
    for(k=0;k<1<<m;++k)   
    {   
        cpy();   
        for(i=0;i<m;++i)   
            if(1<<i&k)   
                for(j=1;j<=n;++j)   
                    b[j][i+1]=-b[j][i+1];   
        sm=lor();   
        if(sm>smax) smax=sm;   
    }   
       
    for(k=0;k<1<<n;++k)   
    {   
        cpy();   
        for(i=0;i<n;++i)   
            if(1<<i&k)   
                for(j=1;j<=m;++j)   
                    b[i+1][j]=-b[i+1][j];   
        sm=lver();   
        if(sm>smax) smax=sm;   
    }   
       
    printf("%d\n",smax);   
       
    fclose(stdin);   
    fclose(stdout);   
    return 0;   
}