Cod sursa(job #133222)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 7 februarie 2008 21:53:04
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
//elimin
#include<stdio.h>
FILE*fin=fopen("elimin.in","r");
FILE*fout=fopen("elimin.out","w");
int a[8000][16],n,m,stl[8000],str[8000];
void rech(int nod,int dim)
{
  int max=str[nod],aux,mn=nod,st,dr;
  st=nod<<1;dr=st+1;
  if(st<=dim&&str[st]>max){max=str[st];mn=st;}
  if(dr<=dim&&str[dr]>max){max=str[dr];mn=dr;}
  if(mn!=nod)
  {
    aux=str[mn];str[mn]=str[nod];str[nod]=aux;
    rech(mn,dim);
  }
}
void ord()
{
  int i,lh,aux;
  for(i=n/2;i>=1;i--)
    rech(i,n);
  lh=n;
  while(lh>0)
  {
    aux=str[1];str[1]=str[lh];str[lh]=aux;
    lh--;
    rech(1,lh);
  }
}
int main()
{
  int lim,i,j,l,c,aux,nr,k,sum,rez;
  rez=-1000000000;
  fscanf(fin,"%d%d%d%d",&n,&m,&l,&c);
  if(n<m)
  {
    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
	fscanf(fin,"%d",&a[j][n-i+1]);
    aux=n;n=m;m=aux;
    aux=l;l=c;c=aux;
  }
  else for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	   fscanf(fin,"%d",&a[i][j]);
  fclose(fin);
  for(i=1;i<=n;i++)
  {
    stl[i]=0;
    for(j=1;j<=m;j++)
      stl[i]+=a[i][j];
  }
  lim=1<<m;
  for(i=0;i<lim;i++)
  {
    nr=0;
    for(j=0;j<m;j++)
      if(i&(1<<j)) nr++;
    if(nr==c)
    {
      for(j=1;j<=n;j++)
	str[j]=stl[j];
      for(j=0;j<m;j++)
	if(i&(1<<j))
	{
	  for(k=1;k<=1;k++)
	    str[k]-=a[k][j+1];
	}
      ord();
      sum=0;
      for(j=l+1;j<=n;j++)
	sum+=str[j];
      if(sum>rez) rez=sum;
    }
  }
  fprintf(fout,"%d",sum);
  fclose(fout);
  return 0;
}