Cod sursa(job #111694)

Utilizator hadesgamesTache Alexandru hadesgames Data 1 decembrie 2007 18:14:39
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <stdlib.h>
int d[7300],b[1000],r,c,max,a[16][7300];
 int compare( const void* a, const void* b ) {
   int* arg1 = (int*) a;
   int* arg2 = (int*) b;
   if( *arg1 < *arg2 ) return -1;
   else if( *arg1 == *arg2 ) return 0;
   else return 1;
 }              
void back(int x,int n,int m,int c1)
{
	int i,j,nr=0;
	if (x==m+1)
	{
		for (i=0;i<=n;i++)
		{
			b[i]=0;
		}
		for (i=1;i<=n;i++)
			for (j=1;j<=m;j++)
				if (!d[j])
				{
					b[i-1]+=a[i][j];
				}
		qsort(b,n,sizeof(b[0]),compare);
		nr=0;
		for (i=r;i<n;i++)
			nr+=b[i];
		if (max<nr)
			max=nr;
				
	}
	else
	{
		if (m-x+1>c-c1)
		{
			d[x]=0;
			back(x+1,n,m,c1);
		}
		if (c1<c)
		{
			d[x]=1;
			back(x+1,n,m,c1+1);
		}
	}
}
int main()
{
	FILE *in,*out;
	int i,j,n,m;
	in=fopen("elimin.in","r");
	out=fopen("elimin.out","w");
	fscanf(in,"%d%d%d%d",&n,&m,&r,&c);
	max=-1;
	if (m<=n)
	{
		for (i=1;i<=n;i++)
			for (j=1;j<=m;j++)
				fscanf(in,"%d",&a[i][j]);
			back(1,n,m,0);
	}
	else
	{
		for (i=1;i<=n;i++)
			for (j=1;j<=m;j++)
				fscanf(in,"%d",&a[j][m-i+1]);
		back(1,m,n,0);
		
	}

	fprintf(out,"%d\n",max);
	fclose(in);
	fclose(out);
	return 0;
}