Cod sursa(job #1731062)

Utilizator preda.andreiPreda Andrei preda.andrei Data 18 iulie 2016 11:54:22
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <set>

using namespace std;

#define NMAX 17

int mat[NMAX][NMAX];
long long sumaLinie[NMAX];
long long sumaColoana[NMAX];

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

    int n, m;
    fin >> n >> m;

    long long sumaMatrice = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            fin >> mat[i][j];
            sumaMatrice += 1LL * mat[i][j];
            sumaLinie[i] += 1LL * mat[i][j];
            sumaColoana[j] += 1LL * mat[i][j];
        }
    }

    long long sumaMax = sumaMatrice;

    for (int i = 0; i < (1 << n); ++i) {
        long long sumaCurenta = sumaMatrice;
        set<int> liniiFolosite;

        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                liniiFolosite.insert(n - j);
                sumaCurenta -= 2 * sumaLinie[n - j];
            }
        }

        for (int j = 1; j <= m; ++j) {
            long long sumaAux  = sumaCurenta;

            sumaAux -= 2 * sumaColoana[j];

            for (int linie : liniiFolosite) {
                sumaAux += 4LL * mat[linie][j];
            }

            sumaCurenta = max(sumaCurenta, sumaAux);
        }

        sumaMax = max(sumaMax, sumaCurenta);
    }

    fout << sumaMax << "\n";
    return 0;
}