Cod sursa(job #149978)

Utilizator znakeuJurba Andrei znakeu Data 6 martie 2008 13:51:21
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <stdlib.h>

int v[7300][16];
int sl[7300];
int n,m,R=0,C=0,max=0;

int cmp(const void *a, const void *b)
{
	int x=*(int*)a,y=*(int*)b;
	return x-y;	
}

int sumlin(int c)
{
	int i,j,t,s=0;
	for (i=0; i<m; ++i)
	{
		for (sl[i]=0,j=0,t=c; j<n; j++,t=t>>1)
			sl[i]+=v[i][j]*(t & 1);
		s+=sl[i];
	}
	qsort(sl,m,sizeof(sl[0]),cmp);
	for (i=0; i<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)
		{
			l+=t&1;
			t=t>>1;
		}
		if (l==n-C)
		{
			t=sumlin(i);
			if (t>max)
				max=t;
		}
	}		
}


int main()
{
	FILE *in  = fopen("elimin.in","r");
	FILE *out = fopen("elimin.out","w");
	
	int i,j,t;
	
	fscanf(in,"%d%d%d%d",&m,&n,&R,&C);
	if (n>15)
	{
		t=n; n=m; m=t;
		t=R; R=C; C=t;
		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",max);
	
	fclose(in);
	fclose(out);
	return 0;
}