Cod sursa(job #494565)

Utilizator chrissBota Cristian chriss Data 21 octombrie 2010 23:35:53
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>
#define MIN -256000001

int a[17][17],i,j,k=1,m,n,p,sum,smax=MIN,scp,scn,lim;

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",&a[i][j]);
	while(k<=m)
    {
        scp=0;
        scn=0;
        for(p=1; p<=n; ++p)
        {
            scp+=a[p][k];
            scn-=a[p][k];
        }
        if(scp>scn)
            sum+=scp;
        else
            sum+=scn;
        k++;
    }
    if(sum>smax)
        smax=sum;

    lim=1<<n;
    for(i=1; i<lim; ++i)
    {
        for(j=0; j<n; ++j)
        {
            if(i&(1<<j))
            {
                for(k=1; k<=m; ++k)
                    a[j][k]=-a[j][k];
            }
        }
        k=1;
        sum=0;
        while(k<=m)
        {
            scp=0;
            scn=0;
			for(p=1; p<=n; ++p)
            {
                scp+=a[p][k];
                scn-=a[p][k];
            }
            if(scp>scn)
                sum+=scp;
            else
                sum+=scn;
            k++;
        }
        if(sum>smax)
            smax=sum;
    }
	printf("%d",smax);
    return 0;
}