Cod sursa(job #135155)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 13 februarie 2008 10:44:56
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 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,
i1,i2,i3,i4,i5,i6,i7,ss[8][600];
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)
	{ for(i1=   0;i1<= 7;i1++)
	  {for(j=0;j<=n;j++)ss[0][j+1]+=a[i1][j];
	   for(i2=i1+1;i2<= 8;i2++)
	   {for(j=0;j<=n;j++)ss[1][j+1]=ss[0][j+1]+a[i2][j];
	    for(i3=i1+1;i3<= 9;i3++)
	    {for(j=0;j<=n;j++)ss[2][j+1]=ss[1][j+1]+a[i3][j];
	     for(i4=i1+1;i4<=10;i4++)
	     {for(j=0;j<=n;j++)ss[3][j+1]=ss[2][j+1]+a[i4][j];
	      for(i5=i1+1;i5<=11;i5++)
	      {for(j=0;j<=n;j++)ss[4][j+1]=ss[3][j+1]+a[i5][j];
	       for(i6=i1+1;i6<=12;i6++)
	       {for(j=0;j<=n;j++)ss[5][j+1]=ss[4][j+1]+a[i6][j];
		for(i7=i1+1;i7<=13;i7++)
		{for(j=0;j<=n;j++)s[j+1]=ss[5][j+1]+a[i7][j];
		 for(i=n/2;i>=1;i--)heapdown(i,n);
		 for(i=n;i>=c;i--){swap(1,i);heapdown(1,i-1);}
		 sc=0;
		 for(i=c+1;i<=n;i++) sc+=s[i];
		 if(sc>sol)sol=sc;
		}
	       }
	      }
	     }
	    }
	   }
	  }
	  fprintf(g,"%ld\n",sol);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);}
}