Cod sursa(job #1070418)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 31 decembrie 2013 23:28:37
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.1 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

ifstream fin("elimin.in");
ofstream fout("elimin.out");

#define NMAX 700

int i, j, M, N, R, C;
int ANS;

int x[NMAX];
int a[NMAX][NMAX];

int Sum[NMAX];
bool Used[NMAX];

void solve() {
	memset(Sum, 0, sizeof(Sum));
	int c, l;
	for (c = 1; c <= M; ++c) {
		if (!Used[c]) 
			for (l = 1; l <= N; ++l) Sum[l] += a[l][c];
	}
	//sort(Sum + 1, Sum + N + 1);
	nth_element(Sum + 1, Sum + R, Sum + N + 1);
	int cnt = 0;
	for (l = R + 1; l <= N; ++l) cnt += Sum[l];
	if (cnt > ANS) ANS = cnt;
}

void back(int k) {
	if (k == C + 1) solve();
	else {
		for (int i = x[k - 1] + 1; i <= M; ++i) {
			if (!Used[i]) {
				x[k] = i;
				Used[i] = true;
				back(k + 1);
				Used[i] = false;
			}
		}
	}
}

int main() {
	fin >> N >> M >> R >> C;
	if (M <= N) {
		for (i = 1; i <= N; ++i) 
			for (j = 1; j <= M; ++j) 
				fin >> a[i][j];
	}
	else {
		for (i = 1; i <= N; ++i) 
			for (j = 1; j <= M; ++j) 
				fin >> a[j][i];
		swap(N, M); swap(R, C);
	}
	back(1);
	fout << ANS << '\n';
	return 0;
}