Cod sursa(job #487157)

Utilizator Teodor94Teodor Plop Teodor94 Data 23 septembrie 2010 22:44:18
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<cstdio>
#include<string>
#include<algorithm>

using namespace std;

const int N=555;
const int M=20;

int a[N][N],n,m,r,c,sol[M],s[N],s2[N],best;

void read()
{
	scanf("%d%d%d%d",&n,&m,&r,&c);
	int i,j;
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
	if (n<m)
	{
		for (i=1;i<=n;++i)
			for (j=1;j<=m;++j)
				if (j>i)
					swap(a[i][j],a[j][i]);
		swap(n,m);
		swap(r,c);
	}
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			s[i]+=a[i][j];
}

void solve()
{
	int i,j,sum=0;
	memcpy(s2,s,sizeof(s));
	for (i=1;i<=c;++i)
		for (j=1;j<=n;++j)
			s2[j]-=a[j][sol[i]];
	sort(s2+1,s2+n+1);
	for (i=r+1;i<=n;++i)
		sum+=s2[i];
	if (sum>best)
		best=sum;
}

void back(int k)
{
	if (k==c+1)
	{
		solve();
		return;
	}
	for (int i=sol[k-1]+1;i<=m;++i)
	{
		sol[k]=i;
		back(k+1);
	}
}

int main()
{
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	read();
	back(1);
	printf("%d\n",best);
	return 0;
}