Cod sursa(job #43101)

Utilizator g3ppyStoian Vlad g3ppy Data 29 martie 2007 20:19:16
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
FILE *fin,*fout;
long smax=-10000000;
int m,n,r,c;
int min[550],mins[550],sum[550],viz[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 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<r;j++) sp-=min[j];
     return sp;
     }

void back (int k)
   {int i,j;
    long s;
   if (k==c)
      {
      s=suma();
      if (smax<s) smax=s;
      return;
      }
   for (i=k;i<m;i++)
      {
      if (viz[i]!=1)
	 {if (k==0&&i==(m-c+1)) return;
	 viz[i]=1;
	 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;
	 }

      }

   }

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);
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);

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