Cod sursa(job #8382)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 24 ianuarie 2007 18:24:55
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 15;
const int MMAX = 7680;

int N, M, R, C;
bool V[NMAX], W;
int A[NMAX][MMAX];
int SMAX;

void read() {
	FILE *fin = fopen("elimin.in", "rt");
	int i, j;

	fscanf(fin, " %d %d %d %d", &N, &M, &R, &C);

	if (M < N) W = true;

	for (i = 0; i < N; ++i)
		for (j = 0; j < M; ++j)
			if (W)
				fscanf(fin, " %d", &A[j][i]);
			else
				fscanf(fin, " %d", &A[i][j]);

	if (W) swap(N, M), swap(R, C);

	fclose(fin);
}

void wipe() {
	int T[MMAX];
	int i, j, sm;

	for (sm = 0, i = 0; i < M; ++i) {

		for (T[i] = 0, j = 0; j < N; ++j)
			if (!V[j]) T[i] += A[j][i];
	
		sm += T[i];
	}
	
	sort(T, T + M);

	for (i = 0; i < C; ++i) 
		sm -= T[i];
	
	SMAX >?= sm;
}

void select(int k, int last) {
	if (k == R)
		wipe();
	else {
		int i;

		for (i = last + 1; i < N; ++i) {
			V[i] = true;
			select(k + 1, i);
			V[i] = false;
		}
	}
}

void write() {
	FILE *fout = fopen("elimin.out", "wt");

	fprintf(fout, "%d\n", SMAX);

	fclose(fout);
}

int main() {
	
	read();

	select(0, -1);

	write();

	return 0;
}