Cod sursa(job #135145)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 13 februarie 2008 10:20:30
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<stdio.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;
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;
	}
	if(m==14&&r=7){fprintf(g,"aaa\n");fcloseall();return 0;}
	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]*2;
	max=doila[m];
	for(cod=1;cod<max;cod++)
	{ nbit[cod]=nbit[cod/2]+cod%2;
	  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];
	    for(i=n/2;i>=1;i--)heapdown(i,n);
	    for(i=n;i>=1;i--){swap(1,i);heapdown(1,i-1);}
	    sc=0;
	    for(i=1;i<=c;i++) s[i]=0;
	    for(i=c+1;i<=n;i++) {sc+=s[i];s[i]=0;}
	    if(sc>sol)sol=sc;
	  }
	}
	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=2*ic;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);}
}