Cod sursa(job #208317)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 15 septembrie 2008 19:42:52
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

long a[701][701];
long vc[1001], st[1001];
long i, j, s, m, n, l, c, aux, x, p;

void calc() {
	long i, j;
	for (i = 1; i <= m; ++i) {
		for (j = 1; j <= n; ++j) {
			if (vc[j] == 0) {
				st[i] += a[i][j];
			}
		}
	}
	sort(st + 1, st + m + 1);
	s = 0;
	for (i = m; i > l; --i) {
		s += st[i];
	}
	for (i = 1; i <= m; ++i) {
		st[i] = 0;
	}
}

int main() {
	long max;
	freopen("elimin.in", "r" ,stdin);
	freopen("elimin.out", "w" ,stdout);
	scanf("%ld %ld %ld %ld", &m, &n, &l, &c);
	for (i = 1; i <= m; ++i) {
		for (j = 1; j <= n; ++j) {
			scanf("%ld", &a[i][j]);
		}
	}
	if (n > m) {
		for (i = 1; i <= m; ++i) {
			for (j = i; j <= n; ++j) {
				aux = a[i][j];
				a[i][j] = a[j][i];
				a[j][i] = aux;
			}
		}
		aux = n;
		n = m;
		m = aux;
		aux = l;
		l = c;
		c = aux;
	}
	for (i = 0; i < (1 << n); ++i) {
		x = i;
		j = 0;
		p = 0;
		while (x > 0) {
			++j;
			vc[j] = x % 2;
			x >>= 1;
			if (vc[j] == 1) {
				++p;
			}
		}
		if (p == c) {
			calc();
		}
		if (s > max) {
			max = s;
		}
	}
	printf("%ld", max);
	return 0;
}