Cod sursa(job #45276)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 1 aprilie 2007 12:35:18
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define nmax 8192
#define FOR(i,s,d) for(i=(s);i<(d);++i)

int n,m,A[16][nmax],r,c,B[nmax],C[nmax],sol;

void test()
{
	int i,aux=0;
	memcpy(C,B,(m<<2));
	sort(C,C+m);
	FOR(i,c,m)
		aux+=C[i];
	sol=max(sol,aux);
}

void doit(int i,int r)
{
	if(r<0||n-i<r)
		return ;
	if(i==n)
	{
		test();
		return ;
	}
	doit(i+1,r-1);
	int j;
	FOR(j,0,m)
		B[j]+=A[i][j];
	doit(i+1,r);
	FOR(j,0,m)
		B[j]-=A[i][j];
}

int main()
{
	int i,j;
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	scanf("%d %d %d %d",&n,&m,&r,&c);
	if(n>m)
	{
		swap(n,m);
		swap(r,c);
		FOR(i,0,m) FOR(j,0,n)
			scanf("%d",&A[j][i]);
	}
	else
		FOR(i,0,n) FOR(j,0,m)
			scanf("%d",&A[i][j]);
	doit(0,r);
	printf("%d\n",sol);
	return 0;
}