Cod sursa(job #1263979)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 15 noiembrie 2014 13:48:32
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>

int n,m,mat[20][20],sgn[20],max_sum=-99999999;

int get_sum()
{
    int ret=0;
    for(int i=0;i<n;++i)
    {
        int s=0;
        for(int j=0;j<m;++j)s+=sgn[j]*mat[i][j];
        if(s<0)s*=-1;
        ret+=s;
    }
    return ret;
}

void backtrack_sgn(int poz)
{
    if(poz<m)
    {
        sgn[poz]=1;
        backtrack_sgn(poz+1);
        sgn[poz]=-1;
        backtrack_sgn(poz+1);
    }
    else
    {
        int current_sum = get_sum();
        if(current_sum>max_sum)max_sum=current_sum;
    }
}

int main()
{
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
    scanf("%d%d",&n,&m);
    if(n>=m)
    {
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)scanf("%d",&mat[i][j]);
    }
    else
    {
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)scanf("%d",&mat[j][i]);
        int aux = n;
        n = m;
        m = aux;
    }
    for(int k=0;k<(1<<m);++k)
        backtrack_sgn(0);
    printf("%d\n",max_sum);
    return 0;
}