Cod sursa(job #3263181)

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

using namespace std;

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

const int NMAX = 32;
int 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
    int i;
    int putere = 1;
    for(i = 0; i <= 32; ++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
    int 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
            int poz = solutie[i] - n; ///a cata cooloana e
            noua_suma = noua_suma - 2*suma_col[poz];
        }
    }
    maxim = max(maxim, noua_suma);
}

int main()
{
    int 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;
    int nr_randuri = m + n;
    int NUMAR = (1 << nr_randuri) - 1;
    for(i = 1; i <= NUMAR; ++i)
    {
        multime(i);
    }
    g << maxim;
    return 0;
}