Cod sursa(job #678034)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 10 februarie 2012 22:14:52
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,r,c,i,j,config,best,lim,s_crt,linie[7500],S[7500],M[7500][20],nr_biti[33000];

void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&r,&c);
	if(m<=n)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&M[i][j]);
				linie[i]+=M[i][j];
			}
	}
	else
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&M[j][i]);
				linie[j]+=M[j][i];
			}
		swap(n,m);
		swap(r,c);
	}
	lim=1<<m;
	nr_biti[1]=1;
	for(i=1;i<=lim/2;i++)
	{
		if(2*i<=lim)nr_biti[2*i]=nr_biti[i];
		if(2*i+1<=lim)nr_biti[2*i+1]=nr_biti[i]+1;
	}
}

void solve()
{
	for(config=0;config<lim;config++)
	{
		if(nr_biti[config]!=c)continue;
		for(i=1;i<=n;i++)
		{	
			S[i]=linie[i];
			for(j=1;j<=m;j++)
			{
				if(config&(1<<(j-1)))
					S[i]-=M[i][j];
			}
		}
		sort(S+1,S+n+1);
		for(i=r+1,s_crt=0;i<=n;i++)s_crt+=S[i];
		best=max(best,s_crt);
	}
	printf("%d\n",best);
}