Cod sursa(job #2376222)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 8 martie 2019 14:16:17
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 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[lung << 1 + 1];
int mat[lung][lung], cmat[lung][lung];
llong smax;

bool line(ushort val)
{
    return val <= N;
}

bool ebun(ushort k)
{
    if(k == 1)
        return true;
    if(line(sol[k]) != line(sol[k - 1]))
        return true;
    return sol[k] > sol[k - 1];
}

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)
        line(sol[i]) ? 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 = 1; i <= N + M; ++i)
    {
        sol[k] = i;
        if(ebun(k))
        {
            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;
}