Cod sursa(job #1195365)

Utilizator MaarcellKurt Godel Maarcell Data 6 iunie 2014 22:55:50
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
#include <iostream>
long long int a[20][20],n,m,max,lin[20],col[20],curent;

long long int Sum()
{
    long long int i,j,summ;
    summ=0;
    for (i=0;i<n;i++)
        for (j=0; j<m; j++) summ+=a[i][j];
    return summ;
}
void back(){
    long long int i,j;
    if (curent > max) max=curent;
    for (i=0; i<n; i++)
        if (lin[i]<0) {
            lin[i]*=-1;
            curent+=2*lin[i];
            for (j=0; j<m; j++) col[j]-=2*a[i][j];

            back();
            for (j=0; j<m; j++) col[j]+=2*a[i][j];
            curent-=2*lin[i];
            lin[i]*=-1;
        }
    for (j=0; j<m; j++)
       if (col[j]<0) {
            col[j]*=-1;
            curent+=2*col[j];
            for (i=0; i<n; i++) lin[i]-=2*a[i][j];

            back();
            for (i=0; i<n; i++) lin[i]+=2*a[i][j];
            curent-=2*col[j];
            col[j]*=-1;
        }



}
int main(){
    long long int i,j;
    freopen("flip.in","r",stdin);
    scanf("%lld %lld\n",&n,&m);
    for (i=0; i<n; i++){
        for (j=0; j<m; j++) {
            scanf("%lld", &a[i][j]);
            col[j]+=a[i][j];
            lin[i]+=a[i][j];
        }

        scanf("\n");
    }


    max=Sum();
    curent=max;
    back();
    freopen("flip.out","w",stdout);
    printf("%lld",max);
    return 0;
}