Cod sursa(job #149972)

Utilizator znakeuJurba Andrei znakeu Data 6 martie 2008 13:41:33
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <algorithm>
#define MAXM 7300
#define MAXN 16

using namespace std;

int v[MAXM][MAXN];
int sl[MAXM];
int n,m,R=0,C=0;
int smax;

bool cmp(int x, int y)
{
	return x>y;
}

int sumlin(int c)
{
	int i,j,t,s=0;
	for (i=0; i<m; ++i)
	{
		sl[i]=0; j=0; t=c;
		for (;j<n; ++j,t=t>>1)
			sl[i]+=v[i][j]*(t & 1);
	}
	sort(sl,sl+n,cmp); s=0;
	for (i=0; i<m-R; ++i)
		s+=sl[i];
	return s;
}

void elimc()
{
	int t,k=1<<n,l,i;
	for (i=0; i<k; ++i)
	{
		t=i; l=0;
		while (t)
		{
			if (t&1)
				++l;
			t=t>>1;
		}
		if (l==n-C)
		{
			t=sumlin(i);
			if (t>smax)
				smax=t;
		}
	}		
}


int main()
{
	FILE *in  = fopen("elimin.in","r");
	FILE *out = fopen("elimin.out","w");
	int i,j;
	
	fscanf(in,"%d%d%d%d",&m,&n,&R,&C);
	if (n>MAXN-1)
	{
		j=n; n=m; m=j;
		j=R; R=C; C=j;
		for (i=0; i<n; ++i)
			for (j=0; j<m; ++j)
				fscanf(in,"%d",&v[j][i]);
	}
	else
	{
		for (i=0; i<m; ++i)
			for (j=0; j<n; ++j)
				fscanf(in,"%d",&v[i][j]);
	}
	elimc();
	fprintf(out,"%d\n",smax);
	
	fclose(in);
	fclose(out);
	return 0;
}