Cod sursa(job #2521614)

Utilizator As932Stanciu Andreea As932 Data 11 ianuarie 2020 11:10:09
Problema Jocul Flip Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n,m;
int joc[17][17];
long long sumMax=0;
int solN[17];
int solM[17];
vector < vector <int> > varM;

int k=0;

void veziSum()
{
    for(int a=0;a<k;a++)
    {
        int sum=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                int el=joc[i][j];
                if(solN[i]==1)
                    el*=-1;
                if(varM[a][j]==1)
                    el*=-1;
                sum+=el;
            }
        if(sum>sumMax)
            sumMax=sum;
    }

}

void adauga()
{
    for(int i=1;i<=m;i++)
        varM[k].push_back(solM[i]);
    k++;
}

void backtrM(int pas)
{
    for(int i=0;i<=1;i++)
    {
        solM[pas]=i;
        if(pas==m)
            adauga();
        else
            backtrM(pas+1);
    }
}

void backtrN(int pas)
{
    for(int i=0;i<=1;i++)
    {
        solN[pas]=i;
        if(pas==n)
            veziSum();
        else
            backtrN(pas+1);
    }
}

int main()
{
    fin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            fin>>joc[i][j];

    varM.resize(1000000);
    backtrM(1);
    backtrN(1);
    fout<<sumMax;

    return 0;
}