Cod sursa(job #2801038)

Utilizator AswVwsACamburu Luca AswVwsA Data 14 noiembrie 2021 18:46:43
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

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

int n, m;
int v[19], col[19], mat[19][19], sum, ans;
bool f[19];
void afis()
{
    for (int i = 1; i <= n; i++)
        cout << v[i] << " ";
}

void flip(int i)
{
    for (int j = 1; j <= m; j++)
    {
        mat[i][j] *= -1;
        sum += 2 * mat[i][j];
    }
}
void backt(int pas)
{
    if (pas == n + 1)
        return ;
    for (int i = v[pas - 1] + 1; i <= n; i++)
    {
        if (f[i])
            continue;
        v[pas] = i;
        f[i] = 1;
        for (int i = 1; v[i]; i++)
            flip(v[i]);
        ans = max(ans, sum);
        /*afis();
        cout << "    " << sum << "\n";*/
        for (int i = 1; v[i]; i++)
            flip(v[i]);
        backt(pas + 1);
        v[pas] = 0;
        f[i] = 0;
    }
}
int main()
{
    fin >> n >> m;
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            fin >> mat[i][j];
            sum += mat[i][j];
            col[j] += mat[i][j];
        }
    ans = sum;
    for (j = 1; j <= m; j++)
        //if (col[j] <= 0)
        {
            int aux = sum;
            for (i = 1; i <= n; ++i)
            {
                mat[i][j] *= -1;
                sum += 2 * mat[i][j];
            }
            ans = max(ans, sum);
            backt(1);
            for (i = 1; i <= n; ++i)
                mat[i][j] *= -1;
            sum = aux;
        }
    fout << ans;
}