Cod sursa(job #119180)

Utilizator ProtomanAndrei Purice Protoman Data 29 decembrie 2007 19:54:15
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
long a[701][701];
long vc[1001],st[1001];
long i,j,s,m,n,l,c,aux,x,p;

int cmp(const int& a, const int& b)
{ 
	return a<b; 
}

void line()
{
	long i,j;
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
			if (vc[j]==0)
				st[i]+=a[i][j];
	sort(st+1,st+n+1,cmp);
	s=0;
	for (i=m;i>l;i--)
		s+=st[i];
	for (i=1;i<=m;i++)
		st[i]=0;
}

int main()
{
	long max;
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	scanf("%ld %ld %ld %ld",&m,&n,&l,&c);
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
			scanf("%ld",&a[i][j]);
	if (n>m)
	{
		for (i=1;i<=m;i++)
			for (j=i;j<=n;j++)
			{
				aux=a[i][j];
				a[i][j]=a[j][i];
				a[j][i]=aux;
			}
		aux=n;
		n=m;
		m=aux;
		aux=l;
		l=c;
		c=aux;
	}
	for (i=0;i<1<<n;i++)
	{
		x=i;
		j=0;
		p=0;
		while (x>0)
		{
			j++;
			vc[j]=x%2;
			x=x/2;
			if (vc[j]==1)
				p++;
		}
		if (p==c)
			line();
		if (s>max)
			max=s;
	}
	printf("%ld",max);
	fclose(stdin);
	fclose(stdout);
}