Cod sursa(job #65705)

Utilizator alextheroTandrau Alexandru alexthero Data 11 iunie 2007 16:07:20
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <algorithm>

#define inf (int)1e9

using namespace std;

int a[16][10005],n,sum,m,r,c,i,j,rez = -inf,aux[16],d[10005];

void show() {
	d[0] = 0;
	for(int j = 1; j <= n; j++) {
		sum = 0;
		for(int i = 1; i <= m; i++)
			if(aux[i] == 0) sum += a[i][j];
		d[++d[0]] = sum;
	}
	sort(d + 1,d + d[0]);
	sum = 0;
	for(int i = c + 1; i <= d[0]; i++) sum += d[i];
	if(rez < sum) rez = sum;
}

void back(int x,int p) {
	for(int i = 0; i < 2; i++) {
		aux[x] = i;
		if(x == m) {
			if(p + aux[x] == r) show();
		}
		else back(x + 1,p + aux[x]);
	}
}

int main() {
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);

	scanf("%d%d%d%d",&m,&n,&r,&c);
	if(m > n) {
		for(int i = 1; i <= m; i++) 
			for(int j = 1; j <= n; j++) scanf("%d",&a[j][m - i + 1]);
		n ^= m ^= n ^= m;
		r ^= c ^= r ^= c;
	}
	else for(int i = 1; i <= m; i++)
			for(int j = 1; j <= n; j++) scanf("%d",&a[i][j]);

	back(1,0);
	printf("%d\n",rez);
			
	return 0;
}