Cod sursa(job #561460)

Utilizator wamfeverDobos Ionut wamfever Data 20 martie 2011 14:49:15
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
#include<cstdio>
#include<cstring>

#define MAx 17

using namespace std;
ofstream fout("flip.out");
int n, m, NR;

int a[MAx][MAx];

int s_L[MAx], s_C[MAx], S, S_MAx;

int sol[33];

int continuare()
{
    for(int i=1; i<=NR; i++)
        if(sol[i]) return 1;
    return 0;
}


void comuta_si_sumeaza()
{
    for(int i=1; i<=NR; i++)
        if(sol[i])
        {
            if(i<=n) S -= s_L[i];
            if(i>n) S -= s_c[i-n];
        }
    if(S>S_MAx) S_MAx = S;
}

void back(int p)
{
    if(p>NR)
    {
        if(continuare())
                comuta_si_sumeaza();
        return;
    }
        sol[p] = 0;
        back(p+1);
        sol[p] = 1;
        back(p+1);
}
int main()
{
    freopen("flip.in", "r", stdin);
    scanf("%d %d", &n, &m); NR=n+m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            scanf("%d", &a[i][j]);
            s_L[i] += a[i][j];
            S += a[i][j];
        }
    for(int j=1; j<=m; j++)
        for(int i=1; i<=n; i++)
            s_C[j] += a[i][j];
    S_MAx = S;
    back(1);
    fout << S_MAx << "\n";
    return 0;

}