Cod sursa(job #2862788)

Utilizator Luca_CristianZamfir Luca-Cristian Luca_Cristian Data 5 martie 2022 20:40:54
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define MAXN 17
int mat[MAXN][MAXN], backupmat[MAXN][MAXN], sumcol[MAXN], newsumcol[MAXN];
int smatrix, newsmatrix;

void flip_line(int l, int m)
{
    for(int c = 1; c <= m; c++)
    {
        newsumcol[c] -= 2 * mat[l][c];
        newsmatrix -= 2 * mat[l][c];
        mat[l][c] = -mat[l][c];
    }
}

void rematrix(int n, int m)
{
     for(int l = 1; l <= n; l++)
        for(int c = 1; c <= m; c++)
            mat[l][c] = backupmat[l][c];
}


int main()
{
    int n, m, l, c;

    fin >> n >> m;

    for(l = 1; l <= n; l++)
        for(c = 1; c <= m; c++)
        {
            fin >> mat[l][c];
            sumcol[c] += mat[l][c];
            newsumcol[c] = sumcol[c];
            backupmat[l][c] = mat[l][c];
            smatrix += mat[l][c];
        }
    newsmatrix = smatrix;


    int i, ci, lin, maxsmatrix = 0;
    for(i = 1; i <= (1 << n) - 1; i++)
    {
        ci = i;
        lin = 0;
        while(ci)
        {
            lin++;
            if((ci & 1) == 1)
               flip_line(lin, m);
            ci >>= 1;
        }

       for(c = 1; c <= m; c++)
       {
          if(newsumcol[c] < 0)
            newsmatrix -= 2 * newsumcol[c];
       }
       if(newsmatrix > maxsmatrix)
        maxsmatrix = newsmatrix;

        rematrix(n, m);
         for(c = 1; c <= m; c++)
             newsumcol[c] = sumcol[c];
        newsmatrix = smatrix;
    }
    fout << maxsmatrix;


    return 0;
}