Cod sursa(job #2218944)

Utilizator anisca22Ana Baltaretu anisca22 Data 6 iulie 2018 15:46:23
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>
#define NMAX 20

using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");

int N, M, mxSum;
int mat[NMAX][NMAX], col[NMAX];

void bk(int nrCol)
{
    if (nrCol > M) ///la finalul liniei
    {
        int bigSum = 0; /// suma pe matrice
        /// PARCURGERE MATRICE
        for (int i = 1; i <= N; i++)
        {
            int smallSum = 0; /// suma pe linii
            for (int j = 1; j <= M; j++)
            {
                if (col[j] == -1)
                    smallSum -= mat[i][j]; ///coloana ii flip-uita
                else smallSum += mat[i][j]; ///coloana nu ii flip-uita
            }
            if (smallSum < 0) ///flip linie
                smallSum = -smallSum;
            bigSum += smallSum;
        }
        mxSum = max(mxSum, bigSum);
        return;
    }
    col[nrCol] = -1; ///flip coloana
    bk(nrCol + 1);
    col[nrCol] = 0; /// unflip coloana
    bk(nrCol + 1);
}

int main()
{
    ///folosesti 'col' ca sa nu trebuiasca sa flip-uiesti literalmente fiecare coloana
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            fin >> mat[i][j];
    bk(1);
    fout << mxSum << "\n";
    return 0;
}