Cod sursa(job #849720)

Utilizator unincepatorDigi Cazan unincepator Data 7 ianuarie 2013 15:47:10
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream>
#include<vector>
#include<iostream>
#include<set>
using namespace std;
vector<vector<long> >table;
long max_sum = 0;
ofstream fout("flip.out");

long flip_and_sum(vector<bool>& bit_map,int n,int m)
{
    int i ,j;
    vector<vector<long> > ctable = table;
    for(i=0;i<n;++i)
            if(bit_map[i])
                for(j=0;j<m;++j)
                    ctable[i][j]*=-1;
    for(j=n;j<m+n;++j)
        if(bit_map[j])
            for(i=0;i<n;i++)
                if(!bit_map[i])
                    ctable[i][j-n]*=-1;
     long s = 0;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
           s += ctable[i][j];
    return s;
}



void back_gen(vector<bool>& bit_map,int k,int n,int m)
{
    if(k == n+m+1)
    {
        long temp = flip_and_sum(bit_map,n,m);

        if (temp > max_sum)
            max_sum = temp;

    }
    else
    {
        bit_map[k] = 0;
        back_gen(bit_map,k+1,n,m);
        bit_map[k] = 1;
        back_gen(bit_map,k+1,n,m);


    }
}
int main()
{

    int n,m,i,j,k;


    ifstream fin("flip.in");
    fin>>n>>m;
    table.resize(n,vector<long>(m,0));
    max_sum = 0;
    vector<bool> bit_map (n+m);
    set<vector<bool> > configs;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
                fin>>table[i][j];
    fin.close();
    back_gen(bit_map,0,n,m);

    fout<<max_sum;
    return 0;
}