Cod sursa(job #135123)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 13 februarie 2008 09:30:13
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
long int m,n,r,c,i,j,a[20][600],aux,max,cod,ccod,nbit,lin,col,s[600],sc,sol;
void heapdown(long int ic,long int nc);
void swap(long int i1,long int i2);
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);
	if(m<=n)for(i=0;i<m;i++)for(j=0;j<n;j++)fscanf(f,"%ld",&a[i][j]);
	else{for(i=0;i<m;i++)
	      for(j=0;j<n;j++)fscanf(f,"%ld",&a[j][i]);aux=m;m=n;n=aux;
		aux=r;r=c;c=aux;
	}
	max=1<<m;
	for(cod=0;cod<max;cod++)
	{ ccod=cod;nbit=0;while(ccod){nbit+=(ccod&1);ccod>>=1;}
	  if(nbit==r)
	  { lin=0;
	    ccod=1;
	    while(ccod<max)
	    { if(ccod&cod) {ccod<<=1;lin++;continue;}
	      for(col=0;col<n;col++)s[col+1]+=a[lin][col];
	      for(i=n/2;i>=1;i--)heapdown(i,n);
	      for(i=n;i>c;i--){ swap(1,i);heapdown(1,i-1);sc+=s[i];s[i]=0;}
	      if(sc>sol)sol=sc;sc=0;
	      lin++;ccod<<=1;
	      for(i=1;i<=c;i++)s[i]=0;
	    }
	  }
	}
	fprintf(g,"%ld\n",sol);
	fcloseall();
	return 0;
}
void swap(long int i1,long int i2)
{
	aux=s[i1];s[i1]=s[i2];s[i2]=aux;
}
void heapdown(long int ic,long int nc)
{
	long int is,is1;
	is=ic<<1;is1=is+1;
	if(is>nc)return;
	if(is<nc)if(s[is]<s[is1])is=is1;
	if(s[ic]<s[is]){swap(is,ic);heapdown(is,nc);}
}