Cod sursa(job #1072597)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 4 ianuarie 2014 17:19:32
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 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;



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)
	{
		calculateSum();
	}
	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));
	V.resize(N);
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			fin >> A[i][j];
		}
	}

	generate(R, N - R, 0);

	fout << Sol << "\n";

#ifdef ONLINE_JUDGE
#else

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