Cod sursa(job #2913568)

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

using namespace std;

ofstream fout("elimin.out");

const long long inf = 1e18;

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

int main(){

	InParser fin("elimin.in");

	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 j = 1; j <= m; j++)
			for(int i = 1; i <= n; i++)
				fin >> mat[i][j];
	}

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

			vector <long long> v;
			for(int j = 1; j <= m; j++){
				long long 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());

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

			ans = max(ans, sum);
		}

	fout << ans << '\n';

	return 0;
}