Mai intai trebuie sa te autentifici.

Cod sursa(job #910878)

Utilizator ELHoriaHoria Cretescu ELHoria Data 11 martie 2013 10:04:11
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;

ifstream cin("elimin.in");
ofstream cout("elimin.out");

const int NMAX = 7294;
int M, N, R, C;
int *a[NMAX], sums[NMAX];
bool use[NMAX];
int e[32];
int ans;

void goLine(int k) {
	if(k == R + 1) {
		for(int j = 0;j < N;j++) {
			sums[j + 1] = 0;
			for(int i = 0;i < M;i++) {
				if(!use[i]) {
					sums[j + 1] += a[i][j];
				}
			}
		}
		nth_element(sums + 1,sums + C,sums + N + 1);
		int sum = 0;
		for(int j = C + 1;j <= N;j++) {
			sum += sums[j];
		}
		ans = max(ans,sum);
	} else {
		for(int j = e[k - 1] + 1;j < M;j++) {
			e[k] = j;
			use[j] = true;
			goLine(k + 1);
			use[j] = false;
		}
	}
}

void goColumn(int k) {
	if(k == C + 1) {
		for(int i = 0;i < M;i++) {
			sums[i + 1] = 0;
			for(int j = 0;j < N;j++) {
				if(!use[j]) {
					sums[i + 1] += a[i][j];
				}
			}
		}
		nth_element(sums + 1,sums + R,sums + M + 1);
		int sum = 0;
		for(int j = R + 1;j <= M;j++) {
			sum += sums[j];
		}
		ans = max(ans,sum);
	} else {
		for(int j = e[k - 1] + 1;j < N;j++) {
			e[k] = j;
			use[j] = true;
			goColumn(k + 1);
			use[j] = false;
		}
	}
}

int main()
{
	cin>>M>>N>>R>>C;
	for(int i = 0;i < M;i++) {
		a[i] = new int[N];
		for(int j = 0;j < N;j++) {
			cin>>a[i][j];
		}
	}
	e[0] = -1 ;
	if(M <= N) {
		goLine(1);
	} else {
		goColumn(1);
	}
	cout<<ans;
	return 0;
}