Cod sursa(job #1447473)

Utilizator SilviuIIon Silviu SilviuI Data 4 iunie 2015 15:58:30
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <stdio.h>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <algorithm>
#include <deque>
#define nmax 18
using namespace std;
int n,m,i,j,linp[nmax],linn[nmax],colp[nmax],coln[nmax],t[nmax][nmax],fr[nmax],frr[nmax],sol=0,maxx;
inline void back(int x)
{
    int i,j;
    maxx=max(maxx,sol);
    for (i=1;i<=n;i++)
         if (linp[i]<linn[i] && fr[i]==0) {
            swap(linp[i],linn[i]); sol=sol+2*(linp[i]-linn[i]); fr[i]=1;
            for (j=1;j<=m;j++) {
                if (t[i][j]<0) colp[j]=colp[j]-t[i][j],coln[j]=coln[j]+t[i][j]; else
                    colp[j]=colp[j]+t[i][j],coln[j]=coln[j]-t[i][j];
            }
            back(x+1);
            swap(linp[i],linn[i]); sol=sol-2*(linn[i]-linp[i]); fr[i]=0;
            for (j=1;j<=m;j++) {
                if (t[i][j]<0) colp[j]=colp[j]+t[i][j],coln[j]=coln[j]-t[i][j]; else
                    colp[j]=colp[j]-t[i][j],coln[j]=coln[j]+t[i][j];
            }
    }
    for (i=1;i<=m;i++)
         if (colp[i]<coln[i] && frr[i]==0){
            swap(colp[i],coln[i]); sol=sol+2*(colp[i]-coln[i]); frr[i]=1;
            for (j=1;j<=n;j++) {
                if (t[j][i]<0) linp[j]=linp[j]-t[j][i],linn[j]=linn[j]+t[j][i]; else
                    linp[j]=linp[j]+t[j][i],linn[j]=linn[j]-t[j][i];
            }
            back(x+1);
            swap(colp[i],coln[i]); sol=sol-2*(coln[i]-colp[i]); frr[i]=0;
            for (j=1;j<=n;j++) {
                if (t[j][i]<0) linp[j]=linp[j]+t[j][i],linn[j]=linn[j]-t[j][i]; else
                    linp[j]=linp[j]-t[j][i],linn[j]=linn[j]+t[j][i];
            }
    }
}
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",&t[i][j]);
        sol=sol+t[i][j];
        if (t[i][j]<0) linn[i]=linn[i]+t[i][j],coln[j]=coln[j]+t[i][j]; else
            linp[i]=linp[i]+t[i][j],colp[j]=colp[j]+t[i][j];
        t[i][j]=2*t[i][j];
    }
for (i=1;i<=n;i++) linn[i]=abs(linn[i]);
for (i=1;i<=m;i++) coln[i]=abs(coln[i]);
maxx=sol; back(1);
printf("%d\n",maxx);
return 0;
}