Cod sursa(job #524566)

Utilizator ooctavTuchila Octavian ooctav Data 22 ianuarie 2011 13:37:16
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

#define II inline
#define LL long long
#define fs first
#define ss second
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + NMAX

const char IN[] = {"elimin.in"};
const char OUT[] = {"elimin.out"};
const int INF = 1000000005;
const int MMAX = 1005;
const int NMAX = 18;

int N, M;
int R, C;
int ainit[NMAX][MMAX], a[MMAX][NMAX];
LL REZ;
int luat[MMAX];

void citi()
{
	scanf("%d%d", &M, &N);
	scanf("%d%d", &R, &C);
	if(M >= N)
		FOR(i, 1, M)	FOR(j, 1, N)	scanf("%d", &a[i][j]);
	else
	{
		FOR(i, 1, M)	FOR(j, 1, N)	scanf("%d", &ainit[i][j]);
		FOR(i, 1, M)	FOR(j, 1, N)	a[j][i] = ainit[i][j];
		swap(M, N);
		swap(R, C);
	}
}

void solutie()
{
	int sum[MMAX] = {0};
	FOR(i, 1, M)	FOR(j, 1, N)	if(!luat[j])	sum[i] += a[i][j];
	sort(sum + 1, sum + M + 1);
	
	LL sol = 0;
	FOR(i, R + 1, M)	sol += sum[i];
	REZ = max(REZ, sol);
}

void back(int k, int nr)
{
	if(k == N + 1)
	{
		if(nr == R)
			solutie();
		return;
	}
	
	luat[k] = 0;
	back(k + 1, nr + luat[k]);
	luat[k] = 1;
	back(k + 1, nr + luat[k]);
}

void scrie()
{
	printf("%d\n", REZ);
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	back(1, 0);
	scrie();
	return 0;
}