Cod sursa(job #3263182)

Utilizator M132M132 M132 M132 Data 13 decembrie 2024 19:19:04
Problema Jocul Flip Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("flip.in");
ofstream g("flip.out");

const int NMAX = 32;
long long solutie[NMAX + 5], suma_col[NMAX + 5], suma_linii[NMAX + 5];
long long suma, maxim, n, m;

void multime(int N)
{
    ///afisez multimea corespunzatoare lui N
    long long i;
    long long putere = 1;
    for(i = 0; i <= 35; ++i)
        solutie[i] = 0;
    for(i = 1; i <= N; ++i)
    {
        if(N&putere)
        {
            solutie[0]++;
            solutie[solutie[0]] = i; ///aici se constuiste multimea
        }
        putere = (putere << 1);
    }
    ///trebuie sa aflu noua suma
    ///nr de la 1 la n sunt pentru linii, nr de la n + 1 la n + m sunt pentru coloane
    long long noua_suma = suma;
    for(i = 1; i <= solutie[0]; ++i)
    {
        if(solutie[i] <= n) ///se shimba o linie
        {
            noua_suma = noua_suma - 2*suma_linii[solutie[i]];
        }
        else
        {
            ///se schima o coloana
            long long poz = solutie[i] - n; ///a cata cooloana e
            noua_suma = noua_suma - 2*suma_col[poz];
        }
    }
    maxim = max(maxim, noua_suma);
}

int main()
{
    long long i, j, v;
    f >> n >> m;
    for(i = 1; i <= n; ++i)
    {
        for(j = 1; j <= m; ++j)
        {
            f >> v;
            suma_linii[i] += v;
            suma_col[j] += v;
        }
        suma += suma_linii[i]; ///suma initiala
    }
    maxim = suma;
    long long nr_randuri = m + n;
    long long NUMAR = (1 << nr_randuri) - 1;
    for(i = 1; i <= NUMAR; ++i)
    {
        multime(i);
    }
    g << maxim;
    return 0;
}