Cod sursa(job #15913)

Utilizator megabyteBarsan Paul megabyte Data 11 februarie 2007 20:53:51
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>
#define NMAX 8192
#define INF "elimin.in"
#define OUF "elimin.out"

int a[NMAX][16],v[NMAX],n,m,r,c,total,bit[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
void qsort(int p,int q)
{
	int i,j,piv,aux;
	i=p;j=q;piv=v[i];
	do{
		while(v[i]<piv) i++;
		while(v[j]>piv) j--;
		if(i<=j)
		{
			aux=v[i];v[i]=v[j];v[j]=aux;
			i++;j--;
		}
	}while(i<j);
	if(i<q) qsort(i,q);
	if(j>p) qsort(p,j);
}
void gensol(int k)
{
	register int i,j,sum;
	for(i=1;i<=n;i++)
	{
		sum=0;
		for(j=0;j<m;j++)
			if(!(k&bit[j])) sum+=a[i][j+1];//printf("%d ",j+1);}
		v[i]=sum;
//		printf("\n");
	}
//	printf("\n");
	qsort(1,n);
	sum=0;
	for(i=r+1;i<=n;i++) sum+=v[i];
//	printf("%d ",sum);
	if(sum>total) total=sum;
}
/*void back(int k)
{
	int i;
	for(i=a;i<=m;i++)
	{
           if(!bit[i])
	   {
	    bit[i]=1;
	    if(k==c) gensol();
	    else back(k+1,a+1);
	    bit[i]=0;
	   }
	}
}*/
int main()
{
        register int i,j,aux,stop;
	FILE *in,*out;
	//gen=fopen(INF,"w");
	//fprintf(gen,"15 
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d %d %d %d",&n,&m,&r,&c);
	if(m<16)
	{
	for(i=1;i<=n;i++)
	        for(j=1;j<=m;j++)
			fscanf(in,"%d",&a[i][j]);
	}
	else
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++) fscanf(in,"%d",&a[j][i]);
		aux=n;n=m;m=aux;
		aux=r;r=c;c=aux;
	}
	/*printf("%d %d\n\n",r,c);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++) printf("%d ",a[i][j]);
		printf("\n");
	}*/
	total=0;stop=1<<m;
	for(i=2;i<stop;i++)
	{
	       	j=0;aux=i;
		while(aux)
		{
			aux=aux&(aux-1);
			j++;
		}
		if(j==c)
//		{
//		printf("%d \n",i);
			gensol(i);
//		}
	}
	if(c<1) gensol(0);
	fprintf(out,"%d",total);
	fclose(in);fclose(out);
	return 0;
}