Cod sursa(job #2109020)

Utilizator flibiaVisanu Cristian flibia Data 19 ianuarie 2018 00:07:09
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
#define N 7210

using namespace std;

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

int n, m, l, c, a[20][N], b[20][N], st[N], vf, lim, bst, rs;

int main(){
	in >> n >> m >> l >> c; 
	if(n <= m)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				in >> a[i][j];
	else
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				in >> a[j][i];
	if(n > m){
		swap(n, m);
		swap(l, c);
	}
	lim = (1 << n);
	for(int mask = 0; mask < lim; mask++){
		if(__builtin_popcount(mask) != l)
			continue;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				b[i][j] = a[i][j];
		for(int i = 0; i < n; i++)
			for(int j = 1; j <= m; j++)
				b[i + 1][j] = b[i][j] + ((1 << i) & mask ? 0 : b[i + 1][j]);
		for(int j = 1; j <= m; j++)
			st[j] = b[n][j];
		sort(st + 1, st + m + 1);
		rs = 0;
		for(int j = c + 1; j <= m; j++)
			rs += st[j];
		bst = max(bst, rs);
	}
	out << bst;
	return 0;
}