Cod sursa(job #377941)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 26 decembrie 2009 23:00:36
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 555
#define PMAX 1<<4
using namespace std;
int v[NMAX][NMAX];
int n,m,r,c,sol[PMAX],S[NMAX],S2[NMAX],best;
void swap(int x,int y)
{
	int t=x;
	x=y;
	y=t;
}
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",&v[i][j]);
			S[i]+=v[i][j];
	if (n<m)
	{
		for (i=1; i<=n; i++)
			for (j=1; j<=m; j++)
				if (i>j)
					swap(v[i][j],v[j][i]);
		swap(n,m);
		swap(r,c);
	}
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			S[i]+=v[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]-=v[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)
{
	int i;
	if (k==c+1)
	{
		solve();
		return;
	}
	for (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;
}