Cod sursa(job #135116)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 13 februarie 2008 09:00:16
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
long int m,n,r,c,i,j,a[16][540],aux,max_cod,st,s[540],sol,n0,n1,p,bit[33000];
void heapdown(long int ic,long int nc);
void prel();
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=1;j<=n;j++)fscanf(f,"%ld",&a[i][j]);
	else{for(i=1;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_cod=1<<m;
	bit[1]=1;if(r==1)prel();
	for(i=2;i<max_cod;i++)
	{bit[i]=bit[i>>1];if(bit[i]==r)prel();
	 bit[i+1]=bit[i]+1;i++;if(bit[i]==r)prel();
	}
	fprintf(g,"%ld\n",sol);
	fcloseall();
	return 0;
}
void prel()
{
	long int ii,jj,kk,sc;
	for(ii=1;ii<=n;ii++)s[ii]=0;
	for(ii=0;ii<m;ii++)
	{kk=1<<ii;if(!(kk&i))
	 for(jj=1;jj<=n;jj++)
	  s[jj]+=a[ii][jj];
	}
	sc=0;
	for(ii=n/2;ii>=1;ii--)heapdown(ii,n);
	for(ii=n;ii>=1;ii--)
	{swap(1,ii);heapdown(1,ii-1);}
	for(ii=c+1;ii<=n;ii++)sc+=s[i];
	if(sc>sol)sol=sc;
}
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);}
}