Cod sursa(job #939970)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 15 aprilie 2013 11:11:13
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
/*#include<cstdio>
#include<cmath>
int a[17][17],c[17],d1[17],s,max=-2147483648,n,m,ca[17][17];
void descompunere(int x){
    int i=0;
    while(x!=0){
        i++;
        d1[i]=x%2;
        x=x/2;
    }
}
void refacere(){
    int i,j;
    for(i=1;i<=n;i++)
        if(d1[i]==1)
            for(j=1;j<=m;j++)
                a[i][j]*=-1;
}
void fc(){
    int i,j;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            c[i]+=a[j][i];
    for(i=1;i<=m;i++){
        if(c[i]<0)
            c[i]*=-1;
        s+=c[i];
    }
    if(s>max)
        max=s;
}
int main(){
    int i,j,nr;
    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]);
            ca[i][j]=a[i][j];
        }
    nr=0;
    while(nr<=pow(2,n+1)){
        descompunere(nr);
        refacere();
        fc();
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                a[i][j]=ca[i][j];
        for(i=1;i<=m;i++)
            c[i]=0;
        s=0;
        nr++;
    }
    printf("%d",max);
    return 0;
}
*/
#include<cstdio>
const int N=17;
int n,m,a[N][N],max;
bool st[N];
void verif(){
    int i,j,suma=0,s;
    for(j=1;j<=m;j++){
        s=0;
        for(i=1;i<=n;i++)
            if(st[i]==1) s+=a[i][j];
            else s-=a[i][j];
        if(s>0)
            suma+=s;
        else
            suma-=s;
    }
    if(suma>max)
        max=suma;
}
void back(int k){
    int i;
    if(k==n+1)
        verif();
    else
        for(i=0;i<2;i++){
            st[k]=i;
            back(k+1);
        }
}
int main(){
    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]);
    back(1);
    printf("%d",max);
    return 0;
}