Cod sursa(job #9177)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 26 ianuarie 2007 22:05:12
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include<stdio.h>
long sir1[8010],sir2[8010],bur[8010],bur2[8010],n,m,var1,var2,i,j,k,ok,sum,min,s,poz,max;
int bin[60];
long partition(long p2 , long q2)
{
 long i=p2-1,aux,j;
 for(j=p2;j<=q2;j++)
if (sir2[j]<=sir2[q2])
 {
i++;
aux=sir2[i];
sir2[i]=sir2[j];
sir2[j]=aux;
 }
return i;
}
long qsort(long p2 , long q2)
{
 long x;
 if (p2<q2)
{
x=partition(p2,q2);
qsort(p2,x-1);
qsort(x+1,q2);
}
return 0;
}
long partition2(long p , long q)
{
 long i=p-1,aux,j;
 for(j=p;j<=q;j++)
if (sir1[j]<=sir1[q])
 {
i++;
aux=sir1[i];
sir1[i]=sir1[j];
sir1[j]=aux;
 }
return i;
}
long qsort2(long p , long q)
{
 long x;
 if (p<q)
{
x=partition2(p,q);
qsort2(p,x-1);
qsort2(x+1,q);
}
return 0;
}
int main()
{
 freopen("elimin.in","r",stdin);
 freopen("elimin.out","w",stdout);
 scanf("%ld %ld %ld %ld",&n,&m,&var1,&var2);
 bin[1]=-1;
 if (n>=m)
 {
 int a1[8010][20];
for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
scanf("%ld",&a1[i][j]);
 ok=n;
 n=m;
 m=ok;
 for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
 sir1[i]+=a1[i][j];
 bur2[i]+=a1[i][j];
 sir2[j]+=a1[i][j];
 bur[j]+=a1[i][j];
}

while (bin[n+1]==0)
 {
 bin[1]++;
 for(k=1;bin[k]>1;bin[k]=0,bin[++k]++);
 ok=0;
 s=0;
 sum=0;
 for(j=1;j<=m;j++)
  sir1[j]=bur2[j];
 for(j=1;j<=n;j++)
if (bin[j]==0) s+=sir2[j];
else
{
sum++;
if ((sum>var2)||(sum+n-j+1<var2))
 {
 ok=1;
 break;
 }
 for(k=1;k<=m;k++)
sir1[k]-=a1[k][j];
}
 if ((sum==var2)&&(!ok))
 {
 qsort2(1,m);
 for(j=1;j<=var1;j++)
s-=sir1[j];
 if (s>max) max=s;
 }
 }
}
else
{
 int a[20][8010];
for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
scanf("%ld",&a[i][j]);
 ok=n;
 n=m;
 m=ok;
 for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
 sir1[i]+=a[i][j];
 bur2[i]+=a[i][j];
 sir2[j]+=a[i][j];
 bur[j]+=a[i][j];
}

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