Cod sursa(job #96678)

Utilizator znakeuJurba Andrei znakeu Data 2 noiembrie 2007 18:12:33
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int v[8000],v2[8000],v3[8000],m,n,r,c,sm=0,first=1;

int comp(const void *a, const void *b)
{
	int *aa=(int*) a, *bb=(int*) b;
	int x=*aa, y=*bb;
	if (x<y)
		return -1;
	if (x>y)
		return 1;
	return 0;
}

	
void elimin(int lc, int ll)
{
	int i,j,sc;
	
	if (ll==0)
	{
		sc=0;
		memmove(v3,v2,n*sizeof(v3[0]));
		qsort(v3,n,sizeof(v3[0]),comp);
		for (i=c; i<n; i++)
			sc+=v3[i];
		if (first)
		{
			sm=sc;
			first=0;
		}
		else 
			if (sc>sm)
				sm=sc;
	}
	else
	{
		for (i=lc; i<m; i++)
		{
			//elimin!
			for (j=0; j<n; j++)
				v2[j]-=v[i*m+j];
			elimin(i+1,ll-1);
			
			//nu elimin :(
			for (j=0; j<n; j++)
				v2[j]+=v[i*m+j];
			elimin(i+1,ll);
		}		
	}
	
	
}
int main()
{
	int i;
	
	FILE *in  = fopen("elimin.in","r");
	FILE *out = fopen("elimin.out","w");
	
	fscanf(in,"%d%d%d%d",&m,&n,&r,&c);
	for (i=0; i<m*n; i++)
	{
		fscanf(in,"%d",&v[i]);
		v2[i%n]+=v[i];
	}
	elimin(0,r);
	fprintf(out,"%d\n",sm);
	
	return 0;
}