Cod sursa(job #120620)

Utilizator slayer4uVictor Popescu slayer4u Data 5 ianuarie 2008 23:20:15
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

long x[600][600], sum[600], maxim, suma, i, j, n, m, r, c, st[600], aux;

void back2(long k, long nr_1)
{
	if (k > n + 1) return;
	if (nr_1 == r)
	{
		for (int j = 1; j <= m; j ++)
		{
			sum[j] = 0;
			for (int i = 1; i <= n; i ++)
				if (!st[i])
					sum[j] += x[i][j];
		}
		sort(sum + 1, sum + m + 1);

		suma = 0;
		for (int i = c + 1; i <= m; i ++)
			suma += sum[i];

		maxim = suma > maxim ? suma : maxim;
	}
	else
	{
		st[k] = 1;
		back2(k + 1, nr_1 + 1);
		st[k] = 0;
		back2(k + 1, nr_1);
	}
}

void back(long k, long nr_1)
{
	if (k > m) return;
	if (nr_1 == c)
	{
		for (int i = 1; i <= n; i ++)
		{
			sum[i] = 0;
			for (int j = 1; j <= m; j ++)
				if (!st[j])
					sum[i] += x[i][j];
		}
		sort(sum + 1, sum + n + 1);

		suma = 0;
		for (int i = r + 1; i <= n; i ++)
			suma += sum[i];

		maxim = suma > maxim ? suma : maxim;
	}
	else
	{
		st[k] = 1;
		back(k + 1, nr_1 + 1);
		st[k] = 0;
		back(k + 1, nr_1);
	}
}

int main()
{
	freopen ("elimin.in", "rt", stdin);
	freopen ("elimin.out", "wt", stdout);

	scanf("%ld %ld %ld %ld", &n, &m, &r, &c);

	for (i = 1; i <= n; i ++)
		for (j = 1; j <= m; j ++)
			scanf("%ld", &x[i][j]);

	if (m <= n)
		back(1, 0);
	else
		back2(1, 0);

	printf("%ld\n", maxim);
	return 0;
}