Cod sursa(job #1527062)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 17 noiembrie 2015 19:43:35
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define Nmax 15
#define Mmax 7300

class FileReader
{
private:
	
	const static int Lmax = 5000;
	int poz;
	char s[Lmax + 1];
	ifstream fin;
	
public:
	
	FileReader(const char* file) {fin.open(file); poz = 0; fin.read(s, Lmax);}
	
	inline void advance()
	{
		++poz;
		if(poz == Lmax)
		{
			fin.read(s, Lmax);
			poz = 0;
		}
	}
	
	FileReader& operator >>(int& x)
	{
		while(!('0' <= s[poz] && s[poz] <= '9')) advance();
		for(x = 0; '0' <= s[poz] && s[poz] <= '9'; advance())
			x = x * 10 + s[poz] - '0';
		
		return *this;
	}
};

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

int m, n, r, c;
int nr[1 << Nmax];
int a[Nmax][Mmax], b[Mmax][Nmax], sum[Mmax];

void solve1() ;
void solve2() ;

int main()
{
	for(int i = 1; i < (1 << Nmax); ++i) nr[i] = 1 + nr[i & (i - 1)];
	
    fin >> m >> n >> r >> c;
    
    if(m < n) solve1();
    else solve2();
    
    return 0;
}

void solve1() // m < n  =>  back pe linii
{
	int i, j, conf, s, smax;
	
	for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) fin >> a[i][j];
	
	for(smax = 0, conf = 0; conf < (1 << m); ++conf)
		if(nr[conf] == r)
	{
		for(j = 0; j < n; ++j) sum[j] = 0;
		
		for(i = 0; i < m; ++i)
			if((conf & (1 << i)) == 0)
				for(j = 0; j < n; ++j) sum[j] += a[i][j];
		
		sort(sum, sum + n, greater<int>());
		for(s = 0, j = 0; j < n - c; ++j) s += sum[j];
		if(s > smax) smax = s;
	}
	
	fout << smax << '\n';
}


void solve2() // m >= n  =>  back pe coloane
{
	int i, j, conf, s, smax;
	
	for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) fin >> b[i][j];
	
	for(smax = 0, conf = 0; conf < (1 << n); ++conf)
		if(nr[conf] == c)
	{
		for(j = 0; j < m; ++j) sum[j] = 0;
		
		for(i = 0; i < m; ++i)
			for(j = 0; j < n; ++j)
				if((conf & (1 << j)) == 0)
					sum[i] += b[i][j];
		
		sort(sum, sum + m, greater<int>());
		for(s = 0, j = 0; j < m - r; ++j) s += sum[j];
		if(s > smax) smax = s;
	}
	
	fout << smax << '\n';
}