Cod sursa(job #2919226)

Utilizator lolismekAlex Jerpelea lolismek Data 16 august 2022 15:32:53
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const long long inf = 1e18;

const int N = 8000;
vector <long long> v[N + 1];
long long sum[N + 1];

int main(){

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

	for(int i = 1; i <= max(n, m); i++)
		v[i].push_back(0);

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++){
			int x;
			fin >> x;
			if(n <= m)
				v[i].push_back(x);
			else
				v[j].push_back(x);
		}

	if(n > m)
		swap(n, m), swap(r, c);

	long long ans = 0;
	for(int msk = 0; msk < (1 << n); msk++){
		if(__builtin_popcount(msk) == r){
			long long tmp = 0;
			for(int j = 0; j < n; j++)
				if((msk & (1 << j)) == 0)
					for(int k = 1; k <= m; k++)
						sum[k] += v[j + 1][k];
			sort(sum + 1, sum + m + 1);
			for(int j = 1; j <= m; j++)
				tmp += sum[j] * (j > c), sum[j] = 0;
			ans = max(ans, tmp);
		}
	}

	fout << ans << '\n';

	return 0;
}