Cod sursa(job #269466)

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

using namespace std;

#define IN "elimin.in","r",stdin
#define OUT "elimin.out","w",stdout

int n,m,r,c,rez;
int v[20][7900];
int sol[20],viz[20],sum[7900];

void citire()
{
	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",&v[i][j]);
}
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)
{
	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 ;
}