Cod sursa(job #1744329)

Utilizator Moise_AndreiMoise Andrei Moise_Andrei Data 19 august 2016 16:58:06
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
int M[20][20];
int c[20][20];
int v[20];
bool marcat[20];
int n, m;
int mx;

void markcol(int col)
{
    for(int i = 1; i <= n; i++)
        M[i][col] *= (-1);
}

int aflare_maxim()
{
    int maxim = 0;
    for(int i = 1; i <= n; i++)
    {
        int s = 0;
        for(int j = 1; j <= m; j++)
            s += M[i][j];
        if(s < 0)
            maxim = maxim + s * (-1);
        else
            maxim += s;
    }
    return maxim;
}

void _back_(int poz)
{
    if(poz > 0)
    {
        for(int i = 1; i <= poz; i++)
            if(v[i])
                markcol(i);
        mx = max(mx, aflare_maxim());
        for(int i = 1; i <= poz; i++)
            markcol(v[i]);
    }
    if(poz == n + 1)
        return;
    for(int i = v[poz - 1] + 1; i <= n; i++)
    {
        v[poz] = i;
        _back_(poz + 1);
    }
}
int main()
{
    in >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            in >> M[i][j];
    _back_(1);
    out << mx;
    return 0;
}