Cod sursa(job #9119)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 26 ianuarie 2007 19:47:34
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#define fin  "elimin.in"
#define fout "elimin.out"
#define Nmax 4000
int n,m,r,c,best,sum[Nmax],used[20],v[20][Nmax];
FILE *in,*out;

int swap(int &a,int &b) { int aux; aux=a; a=b; b=aux; }

void qsort(int st,int dr) {
int i,j,m;
	i=st; j=dr;
	m=sum[(i+j)/2];

	do {
		while (sum[i]<m) ++i;
		while (sum[j]>m) --j;
		if (i<=j) {
		       	swap(sum[i],sum[j]);
	       		++i; --j;
		}	
	} while (i<j);

	if (i<dr) qsort(i,dr);
	if (j>st) qsort(st,j);
}

void go1() {
int i,j,tot=0;

	for (j=1;j<=m;++j) sum[j]=0;

	for (i=1;i<=n;++i) 
		if (!used[i])
		for (j=1;j<=m;++j) { 
			tot+=v[i][j];
			sum[j]+=v[i][j];
		}

	qsort(1,m);

	for (i=1;i<=c;++i) tot-=sum[i];
		
	if (tot>best) best=tot;
}

void go(int x,int p) {
int i;
	if (p==r+1) go1();
	
	else
		for (i=x;i<=n;++i) {
			used[i]=1;
			go(i+1,p+1);
			used[i]=0;
		}
}

int main() {
int i,j;
	in=fopen(fin,"r"); out=fopen(fout,"w");
	fscanf(in,"%i%i%i%i",&n,&m,&r,&c);

	if (n>m) { 
		for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			fscanf(in,"%i",&v[j][i]);
		swap(n,m); swap(r,c);
	}	
	else
		for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			fscanf(in,"%i",&v[i][j]);

	go(1,1);
	
	fprintf(out,"%i\n",best);

	fclose(in); fclose(out);

	return 0;
}