Cod sursa(job #477227)

Utilizator nautilusCohal Alexandru nautilus Data 13 august 2010 21:00:01
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#define dmax 20
using namespace std;

int n,m;
long a[dmax][dmax],sl[dmax],sc[dmax],scurent,smax;

void coloane(long scurent)
{
 int j;
	
 for (j=1; j<=m; j++)
	 if (scurent-2*sc[j] > scurent)
		 scurent-=2*sc[j];
	
 if (scurent>smax)
	 smax=scurent;
}

void bkt(int k)
{
 int j;
	
 if (k==n+1)
	 coloane(scurent); else
	 {
	  scurent+=sl[k];
	  
	  bkt(k+1);
	  
	  scurent-=2*sl[k];
	  for (j=1; j<=m; j++)
		  sc[j]-=2*a[k][j];
	  
	  bkt(k+1);
	  
	  scurent+=sl[k];
	  for (j=1; j<=m; j++)
		  sc[j]+=2*a[k][j];
	 }
	
}

int main()
{
 int i,j;
	
 ifstream fin("flip.in");
 fin>>n>>m;
 for (i=1; i<=n; i++)
	 for (j=1; j<=m; j++)
		 {
		  fin>>a[i][j];
		  sl[i]+=a[i][j];
		  sc[j]+=a[i][j];
		 }
	
  bkt(1);
  
  ofstream fout("flip.out");
  fout<<smax;
  
  fin.close();
  fout.close();

 return 0;
}