Cod sursa(job #2913561)

Utilizator lolismekAlex Jerpelea lolismek Data 15 iulie 2022 11:12:43
Problema Elimin Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define int long long

using namespace std;

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

const int inf = 1e18;

signed main(){

	int n, m, r, c;
	fin >> n >> m >> r >> c;

	bool swaped = false;
	if(n > m)
		swap(n, m), swap(r, c), swaped = true;

	vector <vector <int>> mat(n + 1, vector <int> (m + 1, 0));

	if(!swaped){
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				fin >> mat[i][j];
	}else{
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				fin >> mat[j][i];
	}

	int ans = -inf;
	for(int config = 0; config < (1 << n); config++)
		if(__builtin_popcount(config) == r){

			vector <int> v;
			for(int j = 1; j <= m; j++){
				int s = 0;
				for(int i = 1; i <= n; i++)
					if( (config & (1 << (i - 1))) == 0)
						s += mat[i][j];
				v.push_back(s);
			}
			sort(v.begin(), v.end());

			int sum = 0;
			for(int i = (int)v.size() - 1; i >= c; i--)
				sum += v[i];

			ans = max(ans, sum);
		}

	fout << ans << '\n';

	return 0;
}