Cod sursa(job #1078005)

Utilizator vld7Campeanu Vlad vld7 Data 11 ianuarie 2014 21:41:27
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.42 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("elimin.in");
ofstream g("elimin.out");

int n, m, r, c, ans, Sums[530];
short int A[530][530], B[530][530];
bool elimin[20];

void read() {
	f >> n >> m >> r >> c;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			f >> A[i][j];
}

void rotate() {
	int crt_line = 0, crt_column;
	
	for (int j = 1; j <= m; j++) {
		++crt_line;
		crt_column = 0;
		for (int i = n; i >= 1; i--)
			B[crt_line][++crt_column] = A[i][j];
	}
	
	swap (n, m);
	swap (r, c);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			A[i][j] = B[i][j];
}

void solve() {
	if (n < m)
		rotate();
	
	for (int conf = 0; conf < (1 << m); conf++) {
		int countBits = 0;
		int rez = 0;
		memset (elimin, 0, sizeof(elimin));
		Sums[0] = 0;
		
		for (int x = 0; x < m; x++)
			if (conf & (1 << x)) {
				elimin[x + 1] = 1;
				countBits++;
			}
		
		if (countBits != c)
			continue;
		
		for (int i = 1; i <= n; i++) {
			int sum = 0;
			for (int j = 1; j <= m; j++)
				if (!elimin[j])
					sum += (int)A[i][j];
			Sums[++Sums[0]] = sum;
		}
		
		sort (Sums + 1, Sums + n + 1);
		for (int i = n, cnt = 1; cnt <= n - r; cnt++, i--)
			rez += Sums[i];
		
		ans = max (ans, rez);
	}
}

int main() {
	read();
	solve();
	
	g << ans << '\n';
	
	return 0;
}