Cod sursa(job #1972134)

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

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

long a[17][17],S=0;
int ss[33],sp[33],n,m;

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

long 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 flip(int nr)
{
    int i,j;
    if(nr<=n)
        for(j=1;j<=m;j++)
            a[nr][j]*=(-1);
    else
        for(i=1;i<=n;i++)
            a[i][nr-n]*=(-1);
}

int sol_submult(int k)
{
    return 1;
}

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

int sol_permut(int nr, int k)
{
    return (nr==k ? 1:0);
}

int valid_permut(int k)
{
    int i;
    for(i=1;i<=k-1;i++)
        if(sp[k]==sp[i])
            return 0;
    return 1;
}

void backtrack_permut(int s[33],int nr, int k)
{
    int i;
    long sm=0;
    for(i=1;i<=nr;i++)
    {
        sp[k]=s[i];
        if(valid_permut(k))
        {
            if(sol_permut(nr,k))
            {
                for(int j=1;j<=k;j++)
                {
                    flip(sp[j]);
                    sm=sum();
                    if(sm>S)
                        S=sm;
                }
            }
            backtrack_permut(s,nr,k+1);
        }
    }
}

void backtrack_submult(int k)
{
    int i,j;
    for(i=1;i<=n+m;i++)
    {
        ss[k]=i;
        if(valid_submult(k))
        {
            if(sol_submult(k))
                backtrack_permut(ss,k,1);
            backtrack_submult(k+1);
        }


    }
}



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