Cod sursa(job #204488)

Utilizator AthanaricCirith Gorgor Athanaric Data 24 august 2008 15:50:10
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
int n,m,a[17][17];
char conf[20];
long long smax;
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()
{
	int i,j;
	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]);
	bkt(1);
	printf("%d ",smax);
	return 0;
}