Cod sursa(job #60112)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 12 mai 2007 16:15:35
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
long int m,n,r,c,i,j,a[16][540],aux,cod[16],st,s[540],sol,n0,n1,p;
int heapdown(long int ic,long int nc);
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-c;
	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(i=1;i<=m;i++)
		 if(cod[i])
		  for(j=1;j<=n;j++)
		   s[j]+=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];
		for(j=1;j<=n;j++)s[j]=0;
		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==r) 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 ic,long int nc)
{long int is=0,is1=0;
 if(2*ic>nc)return 0;
 is=2*ic;is1=2*ic+1;
 if(2*ic<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;
}