Cod sursa(job #150026)

Utilizator za_wolfpalianos cristian za_wolf Data 6 martie 2008 15:16:52
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 551
using namespace std;
int cmpf(long a, long b)
{
	return (a<b);
}
long b,z[NMAX],x[NMAX][NMAX],i,j,k,l,a,s,rez,n,m,ln,cl;
char y[17];
void sol()
{
	z[0]=0;
	s=0;
	for (i=1;i<=n;i++)
	{
		z[0]++;
		z[i]=0;
		for (j=1;j<=m;j++)
			if (y[j]==0)
				z[i]+=x[i][j];
		s+=z[i];
	}

/*	a=1;
	while (a)
	{
		a=0;
		for (i=1;i<n;i++)
			if (z[i]>z[i+1])
			{
				a=z[i];
				z[i]=z[i+1];
				z[i+1]=a;
				a=1;
			}
	}
*/
	sort(z+1,z+n+1,cmpf);
	for (i=1;i<=ln;i++)
		s-=z[i];
	if (s>rez)
		rez=s;
}
void back(int p, int k)
{

	if (p<=m&&k<cl)
	{
		back(p+1,k);
		y[p]=1;
		back(p+1,k+1);
		y[p]=0;
	}
	else
	if (k==cl)
		sol();
}
int main()
{
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	scanf("%ld%ld%ld%ld",&n,&m,&ln,&cl);
	rez=-100000;
	if (m<=15)
		for (i=1;i<=n;i++)
			for (j=1;j<=m;j++)
				scanf("%ld",&x[i][j]);
	else
	{
		a=n; n=m; m=a;
		a=ln; ln=cl; cl=a;
		for (j=1;j<=m;j++)
			for (i=1;i<=n;i++)
				scanf("%ld",&x[i][j]);
	}
	back(1,0);
	printf("%ld\n",rez);


	return 0;
}