Cod sursa(job #15086)

Utilizator megabyteBarsan Paul megabyte Data 10 februarie 2007 18:10:19
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#define NMAX 8192
#define INF "elimin.in"
#define OUF "elimin.out"

long int a[NMAX][16],bit[16]={0},v[NMAX],n,m,r,c,total;
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()
{
	register int i,j,sum;
	for(i=1;i<=n;i++)
	{
		sum=0;
		for(j=1;j<=m;j++)
			if(!bit[j]) sum+=a[i][j];
		v[i]=sum;
	}
	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=k;i<=m;i++)
	{
           if(!bit[i])
	   {
	    bit[i]=1;
	    if(k==c) gensol();
	    else back(k+1);
	    bit[i]=0;
	   }
	}
}
int main()
{
        int i,j,aux;
	FILE *in,*out;
	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;
	back(1);
	if(c<1) gensol();
	fprintf(out,"%d",total);
	fclose(in);fclose(out);
	return 0;
}