Cod sursa(job #2854159)

Utilizator ValentValentin Lavric Valent Data 20 februarie 2022 23:11:21
Problema Jocul Flip Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
using namespace std;

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

int n, m, a[20][20], max_sum;

int suma_lin(int k)
{
    int s = 0;
    for (int i = 1; i <= m; ++i)
        s += a[k][i];
    return s;
}

int suma_col(int k)
{
    int s = 0;
    for (int i = 1; i <= n; ++i)
        s += a[i][k];
    return s;
}

void flip2(int k)
{
    for (int i = 1; i <= n; ++i)
        a[i][k] *= -1;
}

void flip(int k)
{
    for (int i = 1; i <= m; ++i)
        a[k][i] *= -1;
}

void back2(int k, int s)
{
    if (k < m)
    {
        back2(k + 1, s);
        flip2(k);
        back2(k + 1, s + 2 * suma_col(k));
        flip2(k);
    }
    else
    {
        if (s > max_sum)
            max_sum = s;
        flip2(k);
        s += 2 * suma_col(k);
        if (s > max_sum)
            max_sum = s;
        flip2(k);
    }
}

void back(int k, int s)
{
    if (k < n)
    {
        back(k + 1, s + suma_lin(k));
        flip(k);
        back(k + 1, s + suma_lin(k));
        flip(k);
    }
    else
    {
        back2(1, s + suma_lin(k));
        flip(k);
        back2(1, s + suma_lin(k));
        flip(k);
    }   
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            fin >> a[i][j];
    back(1, 0);
    fout << max_sum;

    fin.close();
    fout.close();

    return 0;
}