Cod sursa(job #43480)

Utilizator g3ppyStoian Vlad g3ppy Data 30 martie 2007 09:45:33
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <stdio.h>
FILE *fin,*fout;
long smax=-10000000;
int m,n,r,c,l;
int min[550],mins[550],sum[550],viz[550],nr[550],a[550][550];     //550



void reheap(int i)
  { int st=i*2;
    int dr=i*2+1;
    int aux,max;
    max=i;
    if (st<=l&&min[st]<min[max])
       max=st;
    if (dr<=l&&min[dr]<min[max])
       max=dr;
    if (max!=i)
     { aux=min[i];
       min[i]=min[max];
       min[max]=aux;
       reheap(max);
       }
  }


void hsort(int n,int m)
{
l=n;
int i,aux;
for (i=n/2;i>=1;i--)
    reheap(i);
for (i=n;i>=n-m+1;i--)
    { aux=min[i];
      min[i]=min[1];
      min[1]=aux;
      l--;
      reheap(1);
    }
}



int suma(int lim,int li)
     {int j,nr2=1;
     long sp=0;
     for (j=0;j<li;j++)
	   {
	   min[nr2++]=sum[j];
	   sp+=sum[j];
	   }
     hsort(li,lim);
     for (j=li;j>=li-lim+1;j--) sp-=min[j];
     return sp;
     }

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

      }

   }


void back2(int k)
   {int i,j;
    long s;
   if (k==r)
      {
      s=suma(c,n);
      if (smax<s) smax=s;
      return;
      }
   if (k==0) nr[k-1]=-1;
   for (i=nr[k-1]+1;i<=(m-r+k);i++)
      {
      if (viz[i]!=1)
	 {
	 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<m;i++)
	     for (j=0;j<n;j++)
	     {
	     fscanf(fin,"%d",&a[i][j]);
	     sum[i]+=a[i][j];
	     }


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

	     back2(0);

     }

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