Cod sursa(job #135646)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 14 februarie 2008 02:06:38
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<stdio.h>
#include<string.h>
long int n,m,r,c,i,j,a[20][3000],aux,doila[20],max,cod,nbit[70000],
lin,col,s[3000],sc,sol,max1;
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);}
}
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;
	}
	if(r==0)
	{ for(i=0;i<m;i++)
	   for(j=0;j<n;j++)
	    s[j+1]+=a[i][j];
	  for(i=n/2;i>=1;i--)heapdown(i,n);
	  for(i=n;i>=c;i--){swap(1,i);heapdown(1,i-1);}
	  sol=0;
	  for(i=c+1;i<=n;i++) sol+=s[i];
	  fprintf(g,"%ld\n",sol);
	  fcloseall();
	  return 0;
	}
	doila[0]=1;
	for(i=1;i<=m;i++)doila[i]=doila[i-1]<<1;
	max=doila[m];max1=doila[m-1];
	for(cod=0;cod<max1;cod++)
	{nbit[cod<<1]=nbit[cod];nbit[(cod<<1)|1]=nbit[cod]+1;}
	for(cod=0;cod<max;cod++)
	{ if(nbit[cod]==r)
	  { for(lin=0;lin<m;lin++)
	      if(!(cod&doila[lin]))
	       for(col=0;col<n;col++)
		{s[col+1]+=a[lin][col];sc+=s[col+1];}
	    for(i=n/2;i>=1;i--)heapdown(i,n);
	    for(i=n;i>=n-c;i--){sc-=s[1];swap(1,i);heapdown(1,i-1);}
	    if(sc>sol)sol=sc;
	    memset(s,0,sizeof(s));sc=0;
	  }
	}
	fprintf(g,"%ld\n",sol);
	fcloseall();
	return 0;
}