Cod sursa(job #651182)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 19 decembrie 2011 23:38:20
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#define INFINIT 300000000

int matr[17][17];
//int stiva[17];
int n,m;

inline int suma(int nr){
 int i,j;
 int suma=0,suma_col;
   //calculez suam pe coloane
   for(j=0;j<n;j++){
      suma_col=0;
      for(i=0;i<m;i++){
         if((nr&(1<<i))==0){
            suma_col+=matr[i][j];
         }else suma_col-=matr[i][j];         
      }
      if(suma_col<0)suma-=suma_col;
         else suma+=suma_col;
   }

  return suma;

}

int rezolva(){
   int i=0;
   int sum=-INFINIT;
   int aux;
   int doi_la_m=1<<m;
   for(i=0;i<doi_la_m;i++){
      //pt configuratia i
      aux=suma(i);
      if(sum<aux)sum=aux;
   }
   return sum;
}

/*int bktr(){
   int sum=-INFINIT;
   int k=m;
   int loc=k;
   int aux;
   //stiva e initializata cu 0 (nu schimb nimic)
   while(loc>=0){
     if(loc==k){
        aux=suma();
        if(sum<aux)sum=aux;
        loc--;
     }
     stiva[loc]++;
     if(stiva[loc]>1){//pas inapoi
        stiva[loc]=-1;
        loc--;
     }else loc++;
   }
   return sum;
}*/

int main(){
  int i,j;
  freopen("flip.in","r",stdin);
  freopen("flip.out","w",stdout);
  scanf("%d%d",&m,&n);
  for(i=0;i<m;i++)
    for(j=0;j<n;j++)
      scanf("%d",&matr[i][j]);

  printf("%d\n",rezolva());
  return 0;
}