Cod sursa(job #1072606)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 4 ianuarie 2014 17:37:19
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 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;
	
	if( N < M)
	{
		A.resize(N, vector<int>(M));
	
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < M; j++)
			{
				fin >> A[i][j];
			}
		}
	}
	else
	{
		A.resize(M, vector<int>(N));
	
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < M; j++)
			{
				fin >> A[j][i];
			}
		}
		swap(N, M);
		swap(R, C);
	}
	V.resize(N);
	generate(R, N - R, 0);


	fout << Sol << "\n";

#ifdef ONLINE_JUDGE
#else

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