Cod sursa(job #60066)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 12 mai 2007 11:33:49
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
long int m,n,r,c,i,j,a[20][100],aux,cod[20],st,s[100],sol,n0,n1,p;
int heapdown(long int nc,long int ic);
int gnext();
int main()
{
	FILE *f,*g;
	f=fopen("elimin.in","r");
	g=fopen("elimin.out","w");
	fscanf(f,"%ld%ld%ld%ld",&m,&n,&r,&c);
	r=m-r;c=n-n;
	if(m<=n)
	 for(i=1;i<=m;i++)
	  for(j=1;j<=n;j++)
	   fscanf(f,"%ld",&a[i][j]);
	else
	{       for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		fscanf(f,"%ld",&a[j][i]);
		aux=m;m=n;n=aux;
		aux=r;r=c;c=aux;
	}
	for(i=1;i<=r;i++) cod[i]=1;
	do
	{       st=0;
		for(j=1;j<=n;j++)
		 for(i=1;i<=m;i++)
		   s[j]+=cod[i]*a[i][j];
		for(j=n/2;j>=1;j--)
		heapdown(j,n);
		for(j=n;j>=1;j--)
		{ aux=s[1];s[1]=s[j];s[j]=aux;
		  heapdown(1,j-1);
		}
		for(j=1;j<=c;j++)
		st+=s[n+1-j];
		if(st>sol)sol=st;
	}
	while(gnext());
	fprintf(g,"%ld\n",sol);
	fcloseall();
	return 0;
}
int gnext()
{
	n1=0;n0=0;p=m;
	while(cod[p]){p--;n1++;}
	if(n1==m) return 0;
	while(!cod[p]){p--;n0++;}
	cod[p]=0;p++;n0--;cod[p]=1;
	while(n1){p++;cod[p]=1;n1--;}
	while(n0){p++;cod[p]=0;n0--;}
 return 1;
}
int heapdown(long int nc,long int ic)
{long int is=0,is1=0;
 if(ic>nc/2)return 0;
 is=2*ic;is1=2+ic+1;
 if(ic<2*nc){ if(s[is]<s[is1]) is=is1;
 if(s[is]>s[ic]){ aux=s[ic];s[ic]=s[is];s[is]=aux;heapdown(is,nc);}
 return 0;
}
 return 0;
}