Cod sursa(job #257815)

Utilizator f.v.antonFlavius Anton f.v.anton Data 14 februarie 2009 00:15:26
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream.h>
#include <iostream.h>
int n,m,x[40],matr[30][30];long max=-1000000000;
long sum()
{        long s=0;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    s+=matr[i][j];
	return s;
}
void invlin(int lin)
{
	for(int j=1;j<=m;j++)
	  matr[lin][j]*=-1;

}
void invcol(int col)
{

	for(int i=1;i<=n;i++)
	  matr[i][col]*=-1;

}
void tipar(int p)
{       int i,j;   int y[20],c=0;
	for(i=1;i<=p;i++)
	 invlin(x[i]);
	if(sum()>max)
	 max=sum();
	for(j=1;j<=m;j++)
	{    long  s=0;
	 for(i=1;i<=n;i++)
	    s+=matr[i][j];
	 if(s<0)
	{ invcol(j);  y[++c]=j;}
	}
	 if(sum()>max)
	   max=sum();

	for(i=1;i<=p;i++)
	 invlin(x[i]);
	for(i=1;i<=c;i++)
	 invcol(y[i]);

}

int valid(int k)
{
	for(int i=1;i<k;i++)
	  if(x[i]>=x[k])
	    return 0;
	return 1;
}

void back(int k,int p)
{
	for(int i=1;i<=n;i++)
	{	x[k]=i;
		if(valid(k))
		{
			if(k==p)
			 tipar(p);
			 else
			   back(k+1,p);
		}
	}
}

int main()
{
       int i;
	fstream f("flip.in",ios::in),g("flip.out",ios::out);
	f>>n>>m;
	for(i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	     f>>matr[i][j];
	for(i=1;i<=n;i++)
	  back(1,i);
	if(sum()>max)
	 max=sum();
	g<<max;

	f.close();
	g.close();
	return 0;
}