Cod sursa(job #282531)

Utilizator RobybrasovRobert Hangu Robybrasov Data 17 martie 2009 20:45:05
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#define inf 0x7fffffff
#define N 17

int A[N][N],S[N];
int n,m,i,j,maxim;

void rezolva()
{
    int col[N],sum,max;
    max=-inf;
    for (j=1; j<=m; j++)
    {
        sum=0;
        for (i=1; i<=n; i++) //am inmultit cu -1
            if (S[i]) sum+=A[i][j];
            else      sum+=-A[i][j];
        if (sum>max) max=sum, col[j]=1;
        sum=0;
        for (i=1; i<=n; i++) //nu am inmultit
            if (S[i]) sum+=-A[i][j];
            else      sum+=A[i][j];
        if (sum>max) max=sum, col[j]=0;
    }
    sum=0;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            if (S[i]^col[j]) sum+=-A[i][j];
            else             sum+=A[i][j];
    if (sum>maxim) maxim=sum;
}

void calc(int k)
{
    for (int i=0; i<=1; i++)
    {
        S[k]=i;
        if (k==n) rezolva();
        else      calc(k+1);
    }
}

int main()
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	for (i=1; i<=n; i++)
        for (j=1; j<=m; j++) scanf("%d",&A[i][j]);
    maxim=-inf;
    calc(1);
    printf("%d",maxim);

    return 0;
}