Cod sursa(job #788784)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 15 septembrie 2012 21:07:11
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <vector>
using namespace std;

inline int flip(vector< vector<int> > &tabla, unsigned int code); //code:0..(n+m-1)
inline void flip(vector< vector<int> > &tabla, unsigned int code, int &set_suma){ set_suma+=2*flip(tabla,code); }

int main(){
    ifstream fin("flip.in");
    ofstream fout("flip.out");

    int n,m;
    int max_sum=0;
    fin>>n>>m;
    vector< vector<int> > tabla(n,vector<int>(m));
    for(int i=0;i<n;++i) for(int j=0;j<m;++j){ fin>>tabla[i][j]; max_sum+=tabla[i][j]; }

    //vector<bool> setari(n+m,false); //setari[0]..setari[n-1]=rows, setari[n]..setari[n+m-1]=colums.
    bool setari[32]={false,false,false,false,false,false,false,false,false,false,
                     false,false,false,false,false,false,false,false,false,false,
                     false,false,false,false,false,false,false,false,false,false,false,false,};
    bool considered[32]={false,false,false,false,false,false,false,false,false,false,
                     false,false,false,false,false,false,false,false,false,false,
                     false,false,false,false,false,false,false,false,false,false,false,false,};
    int ks=0;
    int curr_sum=max_sum;
    while(ks>-1){
        if(!considered[ks]) considered[ks]=true;
        else if(!setari[ks]){ setari[ks]=true; flip(tabla,ks,curr_sum); }
        else{ setari[ks]=false; considered[ks]=false; flip(tabla,ks,curr_sum); ks--; continue; }

        if(ks==n+m-1){
            if(curr_sum>max_sum) max_sum=curr_sum;

        }
        else ++ks;
    }
    fout<<max_sum<<'\n';
}

inline int flip(vector< vector<int> > &tabla, unsigned int code){
    int sum=0;
    if(code<tabla.size()) for(unsigned i=0;i<tabla[0].size();++i) sum+=(tabla[code][i]=-tabla[code][i]);
    else for(unsigned i=0;i<tabla.size();++i) sum+=(tabla[i][code-tabla.size()]=-tabla[i][code-tabla.size()]);
    return sum;
}