Cod sursa(job #2376332)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 8 martie 2019 14:56:51
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#define lung 17

using namespace std;

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

typedef unsigned short ushort;
typedef long long llong;

ushort N, M, sol[2 * lung - 1];
int mat[lung][lung], cmat[lung][lung];
llong smax;

void comutare_linie(ushort l)
{
    for(ushort c = 1; c <= M;)
        mat[l][c++] *= -1;
}

void comutare_coloana(ushort c)
{
    for(ushort l = 1; l <= N;)
        mat[l++][c] *= -1;
}

llong suma(ushort k)
{
    for(ushort i = 1; i <= N; ++i)
        for(ushort j = 1; j <= M;)
            cmat[i][j] = mat[i][j++];
    for(ushort i = 1; i <= k; ++i)
        sol[i] <= N ? comutare_linie(sol[i]) : comutare_coloana(sol[i] - N);
    llong s = 0;
    for(ushort i = 1; i <= N; ++i)
        for(ushort j = 1; j <= M;)
            s += cmat[i][j++];
    return s;
}

void back(ushort k)
{
    for(ushort i = sol[k - 1] + 1; i <= N + M; ++i)
    {
        sol[k] = i;
        smax = max(smax, suma(k));
        if(k < N + M)
            back(k + 1);
    }
}

int main()
{
    in >> N >> M;
    for(ushort i = 1; i <= N; ++i)
        for(ushort j = 1; j <= M;)
        {
            in >> mat[i][j];
            smax += mat[i][j++];
        }
    back(1);
    out << smax;
    return 0;
}