Cod sursa(job #201903)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 4 august 2008 22:17:59
Problema Elimin Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>

#define FIN "elimin.in"
#define FOUT "elimin.out"
#define N_MAX 8000
#define N_MIN 20

int n;
int N,M,R,C;
int a[N_MIN][N_MAX];
int X[N_MAX];
int Y[N_MIN];
int s1[N_MIN];
int sl[N_MIN],sc[N_MAX];
int SUMA=0,s,S=0;





int max(int a,int b)
{

if (a>b) return a;
    else return b;

}



void swap(int a, int b)
{

a^=b;
b^=a;
a^=b;

}



void quicksort(int li, int ls)
{
int i,j,mij,aux;

i=li;
j=ls;
mij=X[(li+ls)/2];

do
  {
   while (X[i]<mij) ++i;
   while (X[j]>mij) --j;
   if (i<=j)
      {
       aux=X[i];
       X[i]=X[j];
       X[j]=aux;
       ++i;
       --j;
       }
}
while (i<=j);
if (li<j) quicksort(li,j);
if (i<ls) quicksort(i,ls);
}



void back(int k)
{   
int i,j,l;
if (k==R+1)
   {
   for (i=1;i<=N;++i)
       {
       X[i]=sc[i];
       for (j=1;j<=M;++j)
	   {
	   if (Y[j])
	       X[i]-=a[j][i];
	   }
       }
       quicksort(1,N);
       s=S;
       for(i=1;i<=C;++i)
	  {
	  s-=X[i];
	  }
	if (s>SUMA)
	   SUMA=s;
	  }
	  else
	     {
	     for (l=s1[k-1]+1;l<=M;++l)
		 {
		 if (!Y[l])
		    {
		s1[k]=l;
		Y[l]=1;
		S-=sl[l];
		back(k+1);
		Y[l]=0;
		S+=sl[l];
	    }
	}
    }
}



void read()
{

int i,j;

freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);

scanf("%d %d %d %d", &M, &N, &R, &C);

if (M<N)
   {
    for (i=1;i<=M;++i)
	{
	for (j=1;j<=N;++j)
	    {
	    scanf("%d ", &a[i][j]);
	    S+=a[i][j];
	    sl[i]+=a[i][j];
	    sc[j]+=a[i][j];
	    }
	}
    }
    else
       {
	for (i=1;i<=M;++i)
	    {
	    for (j=1;j<=N;++j)
		{
		scanf("%d ", &a[N-j+1][i]);
		S+=a[N-j+1][i];
		sl[N-j+1]+=a[N-j+1][i];
		sc[i]+=a[N-j+1][i];
	    }
	}
    swap(M,N);
    swap(C,R);
    }
}



void solve()
{
read();
back(1);
printf("%d", SUMA);
}


int main()
{
solve();
return 0;
}