Cod sursa(job #1072602)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 4 ianuarie 2014 17:29:09
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iterator>
#include <assert.h>
using namespace std;


const string file = "elimin";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;

vector<bool> V;
vector<vector<int> > A;
int N, M;
int R, C;
int Sol = -INF;
bool flag = false;


void calculateSum2()
{
	vector<int> rowSum(N);
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			if(V[j] == true)
				continue;

			rowSum[i] += A[i][j];
		}
	}
	sort(rowSum.begin(), rowSum.end(), greater<int>());

	int cSum = 0;
	for(int i = 0; i < N - R; i++)
	{
		cSum += rowSum[i];
	}

	if(cSum > Sol)
	{
		Sol = cSum;
	}

}


void calculateSum()
{
	vector<int> columnsSum(M);
	for(int i = 0; i < N; i++)
	{
		if(V[i] == true)
			continue;

		for(int j = 0; j < M; j++)
		{
			columnsSum[j] += A[i][j];
		}
	}
	sort(columnsSum.begin(), columnsSum.end(), greater<int>());

	int cSum = 0;
	for(int i = 0; i < M - C; i++)
	{
		cSum += columnsSum[i];
	}

	if(cSum > Sol)
	{
		Sol = cSum;
	}

}

void generate(int ones, int zeros, int index)
{
	if(ones == 0 && zeros == 0)
	{
		if(flag == false)
		{
			calculateSum();
		}
		else
		{
			calculateSum2();
		}
	}
	else
	{
		if(ones > 0)
		{
			V[index] = true;
			generate(ones - 1, zeros, index + 1);
		}
		if(zeros > 0)
		{
			V[index] = false;
			generate(ones, zeros - 1, index + 1);
		}
	}
}



int main()
{
#ifdef ONLINE_JUDGE
	ostream &fout = cout;
	istream &fin = cin;
#else
	fstream fout(outfile.c_str(), ios::out);
	fstream fin(infile.c_str(), ios::in);
#endif	

	
	fin >> N >> M >> R >> C;
	

	A.resize(N, vector<int>(M));
	
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			fin >> A[i][j];
		}
	}

	if( N < M)
	{
		V.resize(N);
		generate(R, N - R, 0);
	}
	else
	{
		V.resize(M);
		flag = true;
		generate(C, M - C, 0);
	}

	fout << Sol << "\n";

#ifdef ONLINE_JUDGE
#else

	fin.close();
	fout.close();
#endif
}