Cod sursa(job #805643)
Utilizator | Data | 31 octombrie 2012 20:27:11 | |
---|---|---|---|
Problema | Jocul Flip | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.86 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;
}