Cod sursa(job #327575)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 29 iunie 2009 14:43:02
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int maxim;
int n,m,r,c;
int v[20][3000];
int sum[3000];
int sp[3000];
int st[20];

void read()
{
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&r,&c);
	int i,j,aux;
	if(n<m)
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&v[i][j]);
				sum[j]+=v[i][j];
			}
	else
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&v[m-j+1][i]);
				sum[i]+=v[m-j+1][i];
			}
		aux=n;
		n=m;
		m=aux;
		aux=r;
		r=c;
		c=aux;
	}
}

void make()
{
	int i,j,suma=0;
	memset(sp,0,sizeof(sp));
	for(i=1;i<=r;i++)
		for(j=1;j<=m;j++)
			sp[j]=sp[j]-v[st[i]][j];
	for(j=1;j<=m;j++)
		sp[j]+=sum[j];
	sort(sp+1,sp+m+1);
	for(i=c+1;i<=m;i++)
		suma=suma+sp[i];
	if(suma>maxim)
		maxim=suma;
}

void back(int k)
{
	if(k==r+1)
	{
		make();
		return;
	}
	int i;
	for(i=st[k-1]+1;i<=m-r+k;i++)
	{
		st[k]=i;
		back(k+1);
	}
}

int main()
{
	read();
	back(1);
	printf("%d\n",maxim);
	return 0;
}