Cod sursa(job #8076)

Utilizator MariusMarius Stroe Marius Data 23 ianuarie 2007 19:49:46
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const char iname[] = "elimin.in";
const char oname[] = "elimin.out";

#define MAX_M 16
#define MAX_N 1000

int L[MAX_M][MAX_N];

int T[MAX_N][MAX_M];

int sum[MAX_N];

int Res;

int main(void) {
	freopen(iname, "r", stdin);
	int M;
	int N;
	int R;
	int C;
	scanf("%d %d %d %d", & M, & N, & R, & C);
	if (M < MAX_M) {
		for (int i = 0; i < M; ++i) {
			for (int j = 0; j < N; ++j)
				scanf("%d", L[i] + j);
		}
		for (int stp = 0; stp < 1 << M; ++stp) {
			int  cnt = 0;
			for (int i = 0; i < M; ++i)
				cnt += ((stp & (1 << i)) > 0);
			if (cnt == R) {
				for (int j = 0; j < N; ++j) {
					sum[j] = 0;
					for (int i = 0; i < M; ++i)
						if ((stp & (1 << i)) == 0)
							sum[j] += L[i][j];
				}
				sort(sum, sum + N);
				int psum = 0;
				for (int j = C; j < N; ++j)
					psum += sum[j];
				if (Res < psum)
					Res = psum;
			}
		}
	} else {
		for (int i = 0; i < M; ++i) {
			for (int j = 0; j < N; ++j)
				scanf("%d", T[i] + j);
		}
		for (int stp = 0; stp < 1 << N; ++stp) {
			int  cnt = 0;
			for (int j = 0; j < N; ++j)
				cnt += ((stp & (1 << j)) > 0);
			if (cnt == C) {
				for (int i = 0; i < M; ++i) {
					sum[i] = 0;
					for (int j = 0; j < N; ++j)
						if ((stp & (1 << j)) == 0)
							sum[i] += T[i][j];
				}
				sort(sum, sum + M);
				int psum = 0;
				for (int i = R; i < M; ++i)
					psum += sum[i];
				if (Res < psum)
					Res = psum;
			}
		}
	}
	freopen(oname, "w", stdout);
	printf("%d\n", Res);
	return 0;
}