Cod sursa(job #10475)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 28 ianuarie 2007 15:40:09
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <stdio.h>
#include <string.h>

#define NMAX 200
#define MMAX 200

int i,j,n,m,A[NMAX][MMAX],st[NMAX],ll[NMAX],cc[NMAX],l,c,SUM=0,S[NMAX],V[NMAX];

void Quick(int li, int ls)
{
 int i=li, j=ls , x=S[(li+ls)/2], y;
 while (i<=j)
      {
       while (S[i] > x) i++;
       while (S[j] < x) j--;
       if (i<=j)
         {
          y=S[i]; S[i]=S[j]; S[j]=y;
          y=V[i]; V[i]=V[j]; V[j]=y;
          i++; j--;
         }
      }

 if (i<ls) Quick(i,ls);
 if (li<j) Quick(li,j);
}

void MAKE_SUMS_FOR_LINES(void)
{
 int i,j;

 for (i=1;i<=n;i++)
    {
     int sum=0;
     for (j=1;j<=m;j++)
        sum+=A[i][j];
     S[i]=sum;
     V[i]=i;
    }

 Quick(1,n);

 for (i=1;i<=l;i++)
    ll[V[i]]=1;
}

void MAKE_SUMS_FOR_COLS(void)
{
 int i,j;

 for (j=1;j<=m;j++)
    {
     int sum=0;
     for (i=1;i<=n;i++)
        sum+=A[i][j];
     S[j]=sum;
     V[j]=i;
    }

 Quick(1,n);

 for (i=1;i<=c;i++)
    cc[V[i]]=1;
}

void DO_IT(void)
{
 int i,j;
 int SUMO=0;
 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    if (!ll[i] && !cc[j])
      SUMO+=A[i][j];
 if (SUMO > SUM)
   SUM=SUMO;
}

void back(int k, int pch)
{
 int i;
 if (k==n+1)
   {
    int ala=0;
    for (i=1;i<=n;i++)
       if (st[i]==1)
         ala++;
    if (ala == l && pch == 0)
      memcpy(ll,st,sizeof(st));
      else
    if (ala == c && pch == 1)
      memcpy(cc,st,sizeof(st));
    DO_IT();
   }
  else if (k < n+1)
         for (i=0;i<=1;i++)
            {
             st[k]=i;
             back(k+1, pch);
            }
}

int main()
{
 freopen("elimin.in","r",stdin);
 freopen("elimin.out","w",stdout);

 scanf("%d%d%d%d",&n,&m,&l,&c);

 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    scanf("%d",&A[i][j]);

 if (n<m)
   {
    memset(ll, 0 ,sizeof(ll));
    memset(cc, 0 ,sizeof(cc));

    MAKE_SUMS_FOR_COLS();

    SUM=0;
    back(1,0);

    printf("%d",SUM);
   }
  else {
        memset(ll, 0 , sizeof(ll));
        memset(cc, 0 , sizeof(cc));

        MAKE_SUMS_FOR_LINES();

        SUM=0;
        back(1,1);

        printf("%d",SUM);
       }

 fclose(stdin);
 fclose(stdout);
 
 return 0;
}