Cod sursa(job #7342)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 21 ianuarie 2007 13:29:20
Problema Elimin Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 9-a si gimnaziu Marime 1.69 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>

#define FIN "elimin.in"
#define FOUT "elimin.out"
#define A(x,y) *(A+(x-1)*M+y)
#define Sr(x) *(Sr+x)
#define Sc(y) *(Sc+y)
#define St(x) *(St+x)

long *A;
long N, M, max, S, Nr, Nc, R, C;
long *Sr, *Sc;
long *St;

void read_data() {
	long i, x, j;
	freopen(FIN, "r", stdin);
	scanf("%ld %ld %ld %ld", &N, &M, &R, &C);

	Sr = (long*)malloc(sizeof(long) * N);
	Sc = (long*)malloc(sizeof(long) * M);
	A = (long*)malloc(sizeof(long) * N*M);
	memset(Sr,0,sizeof(long)*N);
	memset(Sc,0,sizeof(long)*M);

	for (i=0; i<N; ++i) 
		for (j=0; j<M; ++j) {
			scanf("%ld", &x);
			A(i,j) = x;
			Sr(i) += x;
			Sc(j) += x;
		}
	for (S=0, i=0; i<M; ++i)
		S+=Sc[i];
	fclose(stdin);
}

void eval() {
	long tmp = S, i,j;
	for (i=0; i<N; ++i)
		if ( St(i) ) {
			tmp-= Sr(i);
//			if (tmp<max) return;
		}
	for (j=0; j<M; ++j) 
		if ( St(N+j) ) {
			tmp-= Sc(j);
//			if (tmp<max) return;
		}
	for (i=0; i<N; ++i)
		if ( St(i) ) 
			for (j=0; j<M; ++j)
				if (St(j))
					tmp+=A(i,j);
	if (tmp>max) {
		max = tmp;
/*
		printf("%ld : ", tmp);
		for (i=0; i<N+M; ++i)
			if ( St(i) )
				printf("%ld ", i);
		printf("\n");
		*/
	}
}

void back(long x) {
	if ( x==N+M ) { 
		if ( Nc==C && Nr==R) eval();
		return;
	}
	if (Nr==R && x!=N+1) {
		back(N+1);
		return;
	}
	if (Nc==C && Nr==R) { eval();return; }

	St(x) = 0;
//	if (x<N+M-1)
		back(x+1);
	
	if ( ( x<N && Nr<R ) || ( x>=N && Nc<C ) ) {
		St(x) = 1;
		if ( x<N ) Nr++;
		else Nc++;
//		if (x<N+M-1)
			back(x+1);
	}
}

void write_data() {
	freopen(FOUT, "w", stdout);
	printf("%ld\n", max);
	fclose(stdout);
}

int main() {
	read_data();

	St = (long*)malloc(sizeof(long)*(N+M));
	Nr = 0; Nc = 0;
	back(0);
	write_data();

	return 0;
}