Cod sursa(job #269478)

Utilizator drag0s93Mandu Dragos drag0s93 Data 2 martie 2009 22:33:28
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

#define IN "elimin.in","r",stdin
#define OUT "elimin.out","w",stdout
#define Nmax 8007
#define NMax 21

int n,m,r,c,rez;
int v[NMax][Nmax];
int sol[NMax],viz[NMax],sum[Nmax],b[NMax][Nmax];

void citire()
{
	int nr;
	freopen(IN);
	scanf("%d%d%d%d",&m,&n,&r,&c);
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
		{
			scanf("%d",&nr);
			v[j][m-i+1]=nr;
		}
}
void rotire()
{
	int aux;
	if(n>m)
	{
		aux=n;
		n=m;
		m=aux;
		aux=r;
		r=c;
		c=aux;
		for(int i=1;i<=m;++i)
			for(int j=1;j<=n;++i)
				b[i][j]=v[j][m-i+1];
	}
	else 
		for(int i=1;i<=m;++i)
			for(int j=1;j<=n;++j)
				b[i][j]=v[i][j];
}
void back(int k)
{
	int best;
	if(k==r+1)
	{
		best=0;
		for(int i=1;i<=m;++i)
			sum[i]=0;
		for(int i=1;i<=m;++i)
			for(int j=1;j<=n;++j)
				if(viz[j]==0)
					sum[i]+=b[i][j];
		sort(sum+1,sum+m+1);
		for(int i=c+1;i<=m;++i)
			best+=sum[i];
		if(best>rez)
			rez=best;
		return;
	}
	for(int i=sol[k-1]+1;i<=n-(r-k);++i)
	{
		sol[k]=i;
		viz[i]=1;
		back(k+1);
		viz[i]=0;
	}
}
int main()
{
	freopen(OUT);
	citire();
	rotire();
	back(1);
	printf("%d\n",rez);
	return 0;
}