Cod sursa(job #574384)

Utilizator the_good90Patiu Dan the_good90 Data 7 aprilie 2011 09:30:37
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream.h>

int i,j,k=1,ok,m,n,a[1000][1000],vec[10000],sum,max;
ifstream in("flip.in");
ofstream out("flip.out");

void flip(int k)
{
   int i;
   for(i=1;i<=n;i++)
   a[k][i]=0-a[k][i];
}
int main()
{
  long s;
  in>>m>>n;
  for(i=1;i<=m;i++)
   for(j=1;j<=n;j++)
    in>>a[i][j];
  in.close();
  vec[k]=-1;
  while(k>0)
  {
     ok=0;
     while(vec[k]<1&&!ok)
     {
	vec[k]++;
       if(vec[k]) flip(k);
	ok=1;
     }
     if(ok)
      if(m==k)
      {  sum=0;
	 for(i=1;i<=n;i++)
	 {
	   s=0;
	   for(j=1;j<=m;j++)
	    s+=a[j][i];
	   if(s<0) sum=sum-s;
	   else sum+=s;
	 }
	 if(sum>max) max=sum;
      }
      else
       vec[++k]=-1;
     else
     {
       k--;
       if(vec[k]) flip(k);
     }
  }
  out<<max;
  out.close();
  return 0;
}