Cod sursa(job #2777432)

Utilizator AswVwsACamburu Luca AswVwsA Data 23 septembrie 2021 11:53:33
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");

int mat[18][18], n, m, sum, ans, pr[18][18], S;
long long use;
void solve()
{
    long long  UPB = 1 << (n + m + 1);
    for (use = 1; use < UPB; use++)
    {
        sum = S;
        for (int i = 0; 1LL * (1 << i) <= use; i++)
            if (use & (1 << i))
            {
                int j = i + 1;
                /*{fout << i + 1 << " ";
                cout << i + 1 << " ";
                }*/
                if (j <= n)
                    for (int k = 1; k <= m; k++)
                    {
                        sum -= pr[j][k];
                        pr[j][k] *= -1;
                        sum += pr[j][k];
                    }
                else
                    for (int k = 1; k <= n; k++)
                    {
                        sum -= pr[k][j - n];
                        pr[k][j - n] *= -1;
                        sum += pr[k][j - n];
                    }
            }
        ans = max(ans, sum);
        memcpy(pr, mat, sizeof(mat));
        //fout << "\n";
        //cout << "\n";

    }
}
int main()
{
    int  i, j;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            fin >> mat[i][j];
            S += mat[i][j];
            pr[i][j] = mat[i][j];
        }
    ans = S;
    //backt(1);
    solve();
    //de implementat generarea submultimilor folosind un nr si
    // operatii pe biti
    fout << ans;
}