Cod sursa(job #1839684)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 3 ianuarie 2017 12:46:07
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("flip.in");
ofstream out("flip.out");

const int nMax = 20;
const int mMax = 20;
const int INF = 1000000 * nMax * mMax;

int n, m;
int a[nMax][mMax];
int aux[nMax][mMax];
int sLine[nMax];
int sCol[nMax];
int rasp = -INF;

void citire()
{
    in >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
        {
            in >> a[i][j];
        }
}

void flipLinii(int x)
{
    for(int j = 0; j < m; ++j)
        sCol[j] = 0;

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
        {
            if((x & (1 << i)) == 0)
            {
                aux[i][j] = a[i][j];
            }
            else
            {
                aux[i][j] = -a[i][j];
            }
            sCol[j] += aux[i][j];
        }

    for(int j = 0; j < m; ++j)
    {
        if(sCol[j] < 0)
        {
            for(int i = 0; i < n; ++i)
            {
                aux[i][j] = -aux[i][j];
            }
        }
    }

    int sum = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            sum += aux[i][j];
        }
    }
    rasp = max(rasp, sum);
}

void rezolvare()
{
    int stop = (1 << n);
    for(int i = 0; i < stop; ++i)
        flipLinii(i);
}

void afisare()
{
    out << rasp;
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}