Cod sursa(job #849747)

Utilizator unincepatorDigi Cazan unincepator Data 7 ianuarie 2013 16:18:30
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<fstream>
#include<vector>
#include<iostream>

using namespace std;
vector<vector<long> >table;
long max_sum = 0;


long flip_and_sum(int* 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;
}



int main()
{

    int n,m,i,j;
    ifstream fin("flip.in");
    fin>>n>>m;
    table.resize(n,vector<long>(m,0));
    max_sum = 0;
    long temp;
    int * st = new int[n+m];
    int k = 0,as,ev;
    st[k]=-1;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
                fin>>table[i][j];
    fin.close();
    while(k>-1)
    {
        do{
            if(st[k]<1){
                st[k]++;as = 1;ev = 1;
            }
            else as = 0;
        }while(as && !ev);
        if (as)
            if(k+1 == n+m ){
                    temp = flip_and_sum(st,n,m);
                    if(temp>max_sum)
                        max_sum = temp;
                }
            else{k++;st[k]=-1;}
        else k--;
    }
    delete [] st;
    ofstream fout("flip.out");
    fout<<max_sum;
    fout.close();
    return 0;
}