Cod sursa(job #8774)

Utilizator robbyRobertino robert robby Data 25 ianuarie 2007 15:58:53
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 100
//7295
FILE *f,*g;
long a[nmax][16],v[30];
long sl[nmax],sc[16],slc[nmax],scc[16];

int compare(const void *a,const void *b)
{
   return (*(long*)a-*(long*)b);
}

int main()
{
   long n,m,i,j,r,c,ok,k,aux;
   long suma,min,suma2;
   FILE *f=fopen("elimin.in","rt");
   FILE *g=fopen("elimin.out","wt");
   fscanf(f,"%ld %ld %ld %ld",&m,&n,&r,&c);
   ok=0;
   if (m<n)
	  {
		i=m;
		m=n;
		n=i;
		i=r;
		r=c;
		c=i;
		ok=1;
	  }

   suma=0;
   if (!ok)
	 for (i=0;i<m;i++)
	  {
		for (j=0;j<n;j++)
		  {
			fscanf(f,"%ld",&a[i][j]);
			suma+=a[i][j];
			sl[i]+=(long)a[i][j];
			sc[j]+=(long)a[i][j];
		  }
	  }
	else
	 {
	  for (j=0;j<m;j++)
		{
		  sl[j]=0;
		}
	  for (i=0;i<n;i++)
	   {
		sc[i]=0;
		for (j=0;j<m;j++)
		  {
			fscanf(f,"%ld",&a[j][i]);
			suma+=a[j][i];
			sl[j]+=(long)a[j][i];
			sc[i]+=(long)a[j][i];
		  }
	   }
	 }
   k=1;
   v[k]=-1;
   min=0;
   for (i=0;i<n;i++)
	 scc[i]=sc[i];
   if (c>0)
	{
	 while (k>0)
	 {
	   aux=0;
	   while (aux==0&&v[k]<n-1)
		 {
		   v[k]++;
		   aux=1;
		 }

	   if (aux==0)
		 k--;
		else
		  if (k==c)
			{

			  suma2=suma;
			  for (i=0;i<m;i++)
			   slc[i]=sl[i];

			  for (i=1;i<=k;i++)
				{
				  suma2-=scc[v[i]];
				  for (j=0;j<m;j++)
					slc[j]-=a[j][v[i]];
				}
			  qsort(slc,m,sizeof(long),compare);
			  for (i=0;i<r;i++)
				suma2-=slc[i];

			  if (min<suma2)
				min=suma2;

			}
		   else
			{
			  k++;
			  v[k]=v[k-1];
			}
	  }
	 }
		else
		  {
			  suma2=suma;
			  for (i=0;i<m;i++)
			   slc[i]=sl[i];
			  qsort(slc,m,sizeof(long),compare);
			  for (i=0;i<r;i++)
				suma2-=slc[i];

			  if (min<suma2)
				min=suma2;

		  }
   fprintf(g,"%ld\n",min);
   fclose(f);
   fclose(g);
   return 0;
}