Cod sursa(job #326143)

Utilizator bogyciMobutu Sese Seko bogyci Data 23 iunie 2009 22:15:05
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>

using namespace std;

#define max(a , b) ((a > b) ? a : b)

int main(){
    
    ifstream in;
    ofstream out;
    
    long int N, M, val, sol, MAXsol;
    
    in.open("flip.in");
    in >> N >> M;
    
    long int A[N][M], col[M];

    for (int i=0;i<M;i++) col [i] = 0;
    
    for (int i=0;i<N;i++)
        for (int j=0;j<M;j++){
            
            in >> val;
            
            A[i][j] = val;
            col[j]  += val;            
        }
                    
    in.close();    
    
    sol = 0; MAXsol = 0;
    int p = 1, bck[N+1]; //Backtracking by N, no huge difference for M

    for (int i=1; i<= N; i++) bck[i] = 0;
    
    while (p != 0)
    {
      if (p > N)
      {
        //Test solution here
        sol = 0;        
               
        for (int i=0; i< M; i++)
            sol += max(col[i], -col[i]);        
        
        MAXsol = max(sol, MAXsol);
        
        p--;
        bck[p]++;
      }
      else       
        if (bck[p] == 2)
          {
            bck[p] = 0;
            p--;
            bck[p]++;
            
            for (int j=0;j<M;j++)
            {
              col[j] -= 4*(bck[p]%2-0.5)*A[p-1][j];
            }
            
          }
        else         
          p++;               
    }
    
    out.open("flip.out");    
    out << MAXsol;
    out.close();
    
    return 0;
}