Cod sursa(job #546638)

Utilizator tudorsTudor Siminic tudors Data 5 martie 2011 11:51:28
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>
#include <algorithm>
#define N 101
using namespace std;
int n,m,i,j,r,c,A[N][N],S[N],V[N];
int rez;

FILE *f,*g;

void bt(int k, int p)
{
	int i;
	if (k==r+1)
	{
		int i,j,sum=0;
		for (i=1;i<=n;++i)
			for (j=1;j<=m;++j)
				S[j]+=A[i][j]*V[i];
		sort(S+1,S+m+1);
		for (i=m;i>c;--i)
			sum+=S[i];
		if (sum>rez)
			rez=sum;
		fill(S+1,S+m+1,0);
		return;
	}
	for (i=p+1;i<=n-r+k;++i)
	{
		V[i]=0;
		bt(k+1,i);
		V[i]=1;
	}
}

int main()
{
	f=fopen("elimin.in","r");
	g=fopen("elimin.out","w");
	fscanf(f,"%d %d %d %d",&n,&m,&r,&c);
	if (n<=m)
	{
		for (i=1;i<=n;++i)
		{
			for (j=1;j<=m;++j)
				fscanf(f,"%d",&A[i][j]);
			V[i]=1;
		}
	}
	else
	{
		for (i=1;i<=n;++i)
			for (j=1;j<=m;++j)
				fscanf(f,"%d",&A[j][i]);
		swap(n,m);
		swap(r,c);
	}
	bt(1,0);
	fprintf(g,"%d",rez);
	fclose(f);
	fclose(g);
	return 0;
}