Cod sursa(job #1329226)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 29 ianuarie 2015 11:21:57
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

const int NMAX = 20;
const int inf = 0x3f3f3f3f;

using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");

int N,M,s[NMAX],x,v[NMAX][NMAX],bestanswer;
int sol[NMAX];

void check()
{
    int sum = 0;

    for (int i = 1; i <= N; ++i)
    {
        s[i] = 0;
        for (int j = 1; j <= M; ++j)
        {
            s[i] += sol[j]*v[i][j];
        }
        if (s[i] < 0)
        {
            s[i] = -s[i];
        }
        sum += s[i];
    }

    if (sum > bestanswer)
        bestanswer = sum;
}

void backt(int k)
{
    if (k == M+1)
    {
        check();
        return;
    }

    sol[k] = -1;
    backt(k+1);
    sol[k] = 1;
    backt(k+1);
}

int main()
{
    f >> N >> M;

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            f >> v[i][j];
        }
    }

    bestanswer = -inf;
    backt(1);

    g << bestanswer;

    f.close();
    g.close();
    return 0;
}