Cod sursa(job #1511438)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 26 octombrie 2015 19:18:50
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <cstdio>
using namespace std;

const int dmax = 16;

int A[dmax+1][dmax+1], aux[dmax+1][dmax+1];
int sol[dmax+1];

int N,M,MAX; bool GASIT;

void prelucrare(int k)
{
    int s,sc;

    //COPIEM MATRICEA A
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            aux[i][j] = A[i][j];

    for(int i = 1; i <= k; i++)
        for(int j = 1; j <= M; j++)
        {
            aux[ sol[i] ][j] = - aux[ sol[i] ][j];
        }

    s = 0;

    for(int j = 1; j <= M; j++)
    {
        sc = 0;

        for(int i = 1; i <= N; i++) sc += aux[i][j];

        if(sc < 0) s = s - sc;
        else
            s = s + sc;
    }

    if(GASIT == 0) { MAX = s; GASIT = 1; }
        else
            MAX = max(s,MAX);
}

void bkt(int p)
{
    prelucrare(p-1);

    for(int i = 1 + sol[p-1]; i <= N; i++)
    {
        sol[p] = i;

        bkt(p+1);
    }
}

int main()
{
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);

    scanf("%d %d", &N, &M);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            scanf("%d", &A[i][j]);

    bkt(1);

    printf("%d", MAX);

    return 0;
}