Cod sursa(job #546641)

Utilizator tudorsTudor Siminic tudors Data 5 martie 2011 11:53:59
Problema Elimin Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>
#include <algorithm>
#define N 501
using namespace std;
int n,m,r,c,A[N][N],S[30],V[N],sum;
int rez;

FILE *f,*g;

void bt(int k, int p)
{
	if (k==r+1)
	{
		for (int i=1;i<=n;++i)
			for (int j=1;j<=m;++j)
				S[j]+=A[i][j]*V[i];
		sort(S+1,S+m+1);
		for (int i=m;i>c;--i)
			sum+=S[i];
		if (sum>rez)
			rez=sum;
		sum=0;
		fill(S+1,S+m+1,0);
		return;
	}
	for (int 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 (int i=1;i<=n;++i)
		{
			for (int j=1;j<=m;++j)
				fscanf(f,"%d",&A[i][j]);
			V[i]=1;
		}
	}
	else
	{
		for (int i=1;i<=n;++i)
			for (int 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;
}