Cod sursa(job #1971241)

Utilizator TomaAlimosToma AlimoS TomaAlimos Data 20 aprilie 2017 00:47:55
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<fstream>
using namespace std;

fstream fin("flip.in",ios::in),fout("flip.out",ios::out);

int n,m,f[33];
long a[17][17],S;

void read()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>a[i][j];
}


int valid(int k)
{
    if(k==1)
        return 1;
    if(f[k-1]<f[k])
        return 1;
    return 0;
}

void flip(int x)
{
    int i,j;
    if(x<=n)
        for(j=1;j<=m;j++)
            a[x][j]*=(-1);
    else
        for(i=1;i<=n;i++)
            a[i][x-n]*=(-1);
}
int sum()
{
    long s=0;
    int i, j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            s+=a[i][j];
    return s;
}

void recalc(int k)
{
    int i;
    for(i=1;i<=k;i++)
       flip(f[i]);
}

void backtrack(int k)
{
    long s;
    for(int i=1;i<=n+m;i++)
    {
       f[k]=i;
       if(valid(k))
       {
           recalc(k);
           s=sum();
           if(s>S)
                S=s;
           backtrack(k+1);
       }
    }
}

void print()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            fout<<a[i][j]<<' ';
        fout<<endl;
    }
}


int main()
{
    fin>>n>>m;
    read();
    S=sum();
    backtrack(1);
    fout<<S;
    return 0;
}