Cod sursa(job #8719)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 25 ianuarie 2007 14:24:43
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 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[70];
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);
 int a1[8010][60];
 int a[60][8010];
 bin[1]=-1;
 if (n>=m)
 {
	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[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<=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)<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
{
	for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
		scanf("%ld",&a[i][j]);
 ok=n;
 n=m;
 m=ok;
 ok=var1;
 var1=var2;
 var2=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[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++)
	sir2[j]=bur[j];
 for(j=1;j<=n;j++)
	if (bin[j]==0) s+=sir1[j];
			else
			{
			sum++;
			if ((sum>var1)||((sum+n-j)<var1))
			 {
			 ok=1;
			 break;
			 }
			 for(k=1;k<=m;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);
}