Cod sursa(job #7782)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 22 ianuarie 2007 17:31:30
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<stdio.h>
long sir1[1000],sir2[1000],bur[1000],bur2[1000],n,m,var1,var2,i,j,k,ok,sum,min,s,poz,max;
int bin[400];
int a[1010][1010];
int partition1(long p1 , long q1)
{
 long i=p1-1,aux;
 for(j=p1;j<=q1;j++)
  if (sir1[j]<=sir1[q1])
   {
    i++;
    aux=sir1[i];
    sir1[i]=sir1[j];
    sir1[j]=aux;
   }
  return i;
}
int qsort1(long p1 , long q1)
{
 long x;
 if (p1<q1)
  {
  x=partition1(p1,q1);
  qsort1(p1,x-1);
  qsort1(x+1,q1);
  }
}
int partition(long p2 , long q2)
{
 long i=p2-1,aux;
 for(j=p2;j<=q2;j++)
  if (sir2[j]<=sir2[q2])
   {
    i++;
    aux=sir2[i];
    sir2[i]=sir2[j];
    sir2[j]=aux;
   }
  return i;
}
int qsort(long p2 , long q2)
{
 long x;
 if (p2<q2)
  {
  x=partition(p2,q2);
  qsort(p2,x-1);
  qsort(x+1,q2);
  }
}
int main()
{
 freopen("elimin.in","r",stdin);
 freopen("elimin.out","w",stdout);
 scanf("%ld %ld %ld %ld",&n,&m,&var1,&var2);
 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
  {
   scanf("%ld",&a[i][j]);
   bur2[i]+=a[i][j];
   sir1[i]+=a[i][j];
   sir2[j]+=a[i][j];
   bur[j]+=a[i][j];

  }
 i=1;
 bin[1]=-1;
 if (n<=m)
 while (bin[n+1]==0)
 {
 bin[i]++;
 k=i;
 while (bin[k]>1) {bin[k]=0;bin[++k]++;}
 if (k==n+1) break;
 ok=0;
 s=0;
 sum=0;
 for(j=1;j<=m;j++)
  sir2[j]=bur[j];
 for(j=1;j<=n;j++)
  if (bin[j]==0) s+=sir1[j];
      else
      {
      sum++;
      if (sum>var1) {ok=1;break;}
       for(k=1;k<=m;k++)
        sir2[k]-=a[j][k];
      }
 if (sum!=var1) ok=1;
 if (!ok)
   {
   qsort1(1,n);
   for(j=1;j<=var2;j++)
    s-=sir1[j];
   if (s>max) max=s;
   }
 }
 else
  {
   while (bin[m+1]==0)
 {
 bin[i]++;
 k=i;
 while (bin[k]>1) {bin[k]=0;bin[++k]++;}
 if (k==m+1) break;
 ok=0;
 s=0;
 sum=0;
 for(j=1;j<=n;j++)
  sir1[j]=bur2[j];
 for(j=1;j<=m;j++)
  if (bin[j]==0) s+=sir2[j];
      else
      {
      sum++;
      if (sum>var2) {ok=1;break;}
       for(k=1;k<=n;k++)
        sir1[k]-=a[k][j];
      }
 if (sum!=var2) ok=1;
 if (!ok)
   {
   qsort(1,m);
   for(j=1;j<=var1;j++)
    s-=sir2[j];
   if (s>max) max=s;
   }
 }
  }
 printf("%ld",max);
 printf("\n");
 fclose(stdout);
}