Cod sursa(job #135659)

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