Cod sursa(job #43148)

Utilizator g3ppyStoian Vlad g3ppy Data 29 martie 2007 20:59:28
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <stdio.h>
FILE *fin,*fout;
long smax=-10000000;
int m,n,r,c;
int min[550],mins[550],sum[550],viz[550],nr[550],a[55][55];     //550


void sort(int l, int r)
{
int m = (l + r) >> 1, i, j, k;
if (l == r) return;
sort(l, m);
sort(m + 1, r);
for (i=l, j=m+1, k=l; i<=m || j<=r; )
    if (j > r || (i <= m && min[i] < min[j]))
       mins[k++] = min[i++];
    else
       mins[k++] = min[j++];
for (k = l; k <= r; k++) min[k] = mins[k];
}


int suma(int lim)
     {int j,nr=0;
     long sp=0;
     for (j=0;j<m;j++)
	   {
	   min[nr++]=sum[j];
	   sp+=sum[j];
	   }
     sort(0,nr-1);
     for (j=0;j<lim;j++) sp-=min[j];
     return sp;
     }

void back (int k)
   {int i,j;
    long s;
   if (k==c)
      {
      s=suma(r);
      if (smax<s) smax=s;
      return;
      }
   for (i=nr[k-1]+1;i<=(m-c+k);i++)
      {
      if (viz[i]!=1)
	 {if (k==0&&i==(m-c+1)) return;
	 viz[i]=1;
	 nr[k]=i;
	 for (j=0;j<n;j++) sum[j]-=a[j][i];
	 back (k+1);
	 for (j=0;j<n;j++) sum[j]+=a[j][i];
	 viz[i]=0;
	 }

      }

   }


void back2(int k)
   {int i,j;
    long s;
   if (k==r)
      {
      s=suma(c);
      if (smax<s) smax=s;
      return;
      }
   for (i=nr[k-1];i<=(n-r+k);i++)
      {
      if (viz[i]!=1)
	 {if (k==0&&i==(m-r+1)) return;
	 viz[i]=1;
	 nr[k]=i;
	 for (j=0;j<n;j++) sum[j]-=a[i][j];
	 back2 (k+1);
	 for (j=0;j<n;j++) sum[j]+=a[i][j];
	 viz[i]=0;
	 }

      }

   }


int main()

{int i,j;
fin=fopen("elimin.in","rt");
fout=fopen("elimin.out","wt");
fscanf(fin,"%d %d %d %d\n",&m,&n,&r,&c);

if (n>m){
	   for (i=0;i<n;i++)
	     for (j=0;j<m;j++)
	     {
	     fscanf(fin,"%d",&a[i][j]);
	     sum[i]+=a[i][j];
	     }


	    back(0);
	     }
else {
     for (i=0;i<n;i++)
	 for (j=0;j<m;j++)
	     {
	     fscanf(fin,"%d",&a[i][j]);
	     sum[j]+=a[i][j];
	     }

	     back2(0);

     }

fprintf(fout,"%ld\n",smax);
fcloseall();
return 0;
}