Cod sursa(job #377660)

Utilizator Mishu91Andrei Misarca Mishu91 Data 25 decembrie 2009 18:58:57
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAX_N 1005

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

int N, M, R, C, A[MAX_N][MAX_N], P[MAX_N], S[MAX_N], Sol;

void citire()
{
	fin >> N >> M >> R >> C;

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			fin >> A[i][j];

	if(N > M)
	{
		for(int i = 1; i <= N; ++i)
			for(int j = 1; j <= M; ++j)
				if(i > j)
					swap(A[i][j], A[j][i]);

		swap(N, M);
		swap(R, C);
	}
}

void solve()
{
	for(int i = N; i > N-R; --i)
		S[i] = 1;

	do
	{
		memset(P, 0, sizeof P);
		for(int i = 1; i <= N; ++i)
			for(int j = 1; j <= M; ++j)
				if(S[i] == 0)
					P[j] += A[i][j];

		sort(P+1, P+M+1);
		int s = 0;
		for(int i = C+1; i <= M; ++i)
			s += P[i];
		if(s > Sol)
			Sol = s;
	}
	while(next_permutation(S+1, S+N+1));

	fout << Sol << "\n";
}

int main()
{
	citire();
	solve();
}