Cod sursa(job #586084)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 30 aprilie 2011 13:38:18
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <cstdio>

using namespace std;

const int NMAX = 16;
const int INF = -1000002;
int n,m,sol=INF;
int matrix[NMAX][NMAX];
int sumPoz[NMAX], sumNeg[NMAX];

inline void debug_matrix(){
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j)
            cerr<<matrix[i][j]<<' ';
        cerr<<'\n';
    }
    cerr<<'\n';
}

void read_problem(){
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
    scanf("%d%d",&n,&m);

    int i,j;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j){
            scanf("%d",&matrix[i][j]);
            if (matrix[i][j]>0)
                sumPoz[i]+=matrix[i][j];
            else
                sumNeg[i]-=matrix[i][j];
        }
}

int sum(){
    int s = 0;
    for(int i=0;i<n;++i)
        s+=max(sumPoz[i]-sumNeg[i],sumNeg[i]-sumPoz[i]);
    return s;
}

void flip_column(int k){
    for(int i=0; i<n; ++i){
        sumPoz[i] -= matrix[i][k];
        sumNeg[i] += matrix[i][k];

        matrix[i][k] = -matrix[i][k];
    }
}

void back(int k){
    sol = max(sol,sum());

    if (k == m)
        return;

    for(int i=k; i<n; ++i){
        back(k+1);
        flip_column(i);
        back(k+1);
    }
}



int main()
{
    read_problem();
    back(0);
    printf("%d\n",sol);
    return 0;
}