Cod sursa(job #135641)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 14 februarie 2008 01:37:08
Problema Elimin Scor 0
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 QS(long int st,long int dr);
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];
	  QS(1,n);
	  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];
	    QS(1,n);
	    sc=0;
	    for(i=c+1;i<=n;i++)sc+=s[i];
	    if(sc>sol)sol=sc;
            memset(s,0,sizeof(s));
	  }
	}
	fprintf(g,"%ld\n",sol);
	fcloseall();
	return 0;
}
void QS(long int st,long int dr)
{    long int left,right,middle;
     left= st-1;right= dr+1;middle = st;
     do
     { do left++;while(s[left]>s[middle]);
       do right--;while(s[right]<s[middle]);
       if(left<=right){aux=s[left];s[left]=s[right];s[right]=aux;}
     }while(left<=right);
     if(left<dr)QS(left,dr);
     if(st<j)QS(st,right);
}