Cod sursa(job #6908)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 21 ianuarie 2007 10:42:39
Problema Elimin Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 9-a si gimnaziu Marime 1.17 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXM 105
#define MAXN 7300

int M, N, R, C;
vector< vector<int> > x;
int sc[MAXN], MAX = -0x3f3f3f3f;
int st[MAXM], used[MAXM];

void back(int k)
{
	int i;
	if (k == R)
	{
		int S = 0, j;
		for (i = 0; i < N; i++)
			sc[i] = 0;
		for (i = 0; i < M; i++)
			if (!used[i])
				for (j = 0; j < N; j++)
					sc[j] += x[i][j];
		sort(sc, sc + N);
		for (i = N - 1; i >= C; i--)
			S += sc[i];
		if (S > MAX)
			MAX = S;
		return;
	}
	if (k == 0)
		i = 0;
	else
		i = st[k - 1] + 1;
	for (; i < M; i++)
	{
		used[i] = 1;
		st[k] = i;
		back(k + 1);
		used[i] = 0;
	}
}

int main()
{
	freopen("elimin.in", "rt", stdin);
	freopen("elimin.out", "wt", stdout);
	scanf("%d %d %d %d", &M, &N, &R, &C);
	if (M <= N)
	{
		int i, j, k;
		x.resize(M);
		for (i = 0; i < M; i++)
			for (j = 0; j < N; j++)
			{
				scanf("%d", &k);
				x[i].push_back(k);
			}
	}
	else
	{
		int i, j, k;
		x.resize(N);
		for (i = 0; i < M; i++)
			for (j = 0; j < N; j++)
			{
				scanf("%d", &k);
				x[j].push_back(k);
			}
		i = N; N = M; M = i;
		i = R; R = C; C = i;
	}
	MAX = -0x3f3f3f3f;
	back(0);
	printf("%d\n", MAX);
	return 0;
}