Cod sursa(job #1277703)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 28 noiembrie 2014 00:26:10
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std;
int a[17][17],N,M;
int slin[17],scol[17];
int b[17][17];

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

    scanf("%d%d",&N,&M);
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < M; ++j)
        {
            scanf("%d", &a[i][j]);
            slin[i] = slin[i] + a[i][j];
            scol[j] = scol[j] + a[i][j];
        }
    int best = -INF;
    for(int state = 0; state < (1<<N); ++state)
    {
        int crt = 0,col = 0;
        for(int i = 0; i < N; ++i) /// neg doar liniile
            if(state & (1<<i))
                crt -= slin[i];
            else
                crt += slin[i];
        for(int j = 0; j < M; ++j) /// iau greedy coloanele si vad daca nu cumva era mai bine sa fie si ele negate
        {
            col = 0;
            for(int i = 0; i < N; ++i)
                if(state & (1<<i))
                    col -= a[i][j];
                else
                    col += a[i][j];
            if(col < 0)
                crt -= 2*col;
        }
        if(best < crt)
            best = crt;
    }
    printf("%d\n",best);
    return 0;
}