Cod sursa(job #9113)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 26 ianuarie 2007 19:42:22
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<stdio.h>
#define fin  "elimin.in"
#define fout "elimin.out"
#define Nmax 1000
int n,m,r,c,best,used[20],v[20][Nmax],aux[Nmax][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 a[]) {
int i,j,m;
	i=st; j=dr;
	m=a[(i+j)/2];

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

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

void go1() {
int i,j,tot=0,sum[Nmax]={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,sum);

	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);

	for (i=1;i<=n;++i)
	for (j=1;j<=m;++j)
		fscanf(in,"%i",&aux[i][j]);

	if (n>m) {
		for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			v[j][i]=aux[i][j];
		swap(n,m); swap(r,c);
	}
	else
		for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			v[i][j]=aux[i][j];
	
	go(1,1);
	
	fprintf(out,"%i\n",best);

	fclose(in); fclose(out);

	return 0;
}