Cod sursa(job #586134)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 30 aprilie 2011 13:49:01
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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];
bool checked[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];
    }
}

inline void debug_checked(){
    for(int i=0;i<m;++i)
        cout<<checked[i];
    cout<<'\n';
}

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

    //debug_checked();

    if (k == m)
        return;

    for(int i=k; i<m; ++i)
        if(!checked[i]){

            flip_column(i);
            checked[i]=true;
            back(k+1);

            flip_column(i);
            checked[i]=false;
    }
}



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