Cod sursa(job #203822)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 20 august 2008 10:24:10
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
int N,M,a[17][17];
long long smax;
char conf[20];

FILE *fin=fopen("flip.in","r"),
    *fout=fopen("flip.out","w");

void modificare(){
    for(int i=1;i<=M;i++)
        if(conf[i]==1) for(int j=1;j<=N;j++) a[j][i]*=-1;
}

long long suma(){
    long long st,sp,sn;
    st=0;
    for(int i=1;i<=N;i++){
        sp=sn=0;
        for(int j=1;j<=M;j++)
            if(a[i][j]>0) sp+=a[i][j];
                else sn-=a[i][j];

        if(sp>sn) st=st+sp-sn;
            else st=st+sn-sp;
    }

    return st;
}

void bkt(int k){
    if(k==M+1) {
        modificare();
        long long sum=suma();
        if(sum>smax) smax=sum;
        modificare();
    }
    else
    for(int i=0;i<=1;i++){
        conf[k]=i;
        bkt(k+1);
    }
}

int main(){

    fscanf(fin,"%d %d",&N,&M);

    for(int i=1;i<=N;i++)
    for(int j=1;j<=M;j++)
        fscanf(fin,"%d",&a[i][j]);

    bkt(1);

    fprintf(fout,"%lld\n",smax);

    fclose(fin);
    fclose(fout);

    return 0;
}