Cod sursa(job #189056)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 11 mai 2008 18:54:35
Problema Elimin Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 222
#define N 20
using namespace std;
long long bestS,Suma;
int v[Nmax];
int m,n,c,r;
int a[Nmax][Nmax],b[Nmax][Nmax];
int sol[N];
int rot(int mb[Nmax][Nmax],int ma[Nmax][Nmax])
{	
	for(int i=0;i<=m;++i)
		for(int j=0;j<=n;++j)
			ma[j][m+1-i]=mb[i][j];
	return 0;
}
void roteste()
{
	int aux;
	rot(a,b);
	for(int i=0;i<=n;++i)
		for(int j=0;j<=m+1;++j)
			a[i][j]=b[i][j];
	for(int i=1;i<=n;++i)
		a[i][0]=a[i][m+1];
	aux=r; r=c; c=aux;
	aux=m; m=n; n=aux;
}	
void print()
{
	long long Si=Suma;
	for(int i=1;i<=m;++i)
		v[i]=a[i][0];
	for(int i=1;i<=c;++i)
	{
		Si-=a[0][sol[i]];
		for(int j=1;j<=m;++j)
			v[j]-=a[j][sol[i]];
	}
	sort(v+1,v+m+1); 
	//for(int i=1;i<=m;++i)
	//	printf("%d ",v[i]);
	//printf(" S=%d   ",Si);
	//for(int j=1;j<=c;++j)
	//	printf("%d ",sol[j]);
	//	printf(" :  ");
	for(int i=1;i<=r;++i)
	{
		Si-=v[i];
		//printf("%d ",v[i]);
	}	
	//printf("\n");
	if(Si>bestS)
	{	
		bestS=Si;
		//for(int i=1;i<=c;++i)
		//	printf("%d ",sol[i]);
		//printf("\n");
	}	
}
void back(int x)
{
	if(x==c)
		print();
	else
		for(int i=sol[x]+1;i<=n;++i)
		{
			sol[x+1]=i;
			back(x+1);
		}	
}		
	
int main()
{
	freopen("elimin.in", "r", stdin);
	freopen("elimin.out", "w", stdout);
	scanf("%d%d%d%d", &m,&n,&r,&c);
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
		{
			scanf("%d", &a[i][j]);
			Suma+=a[i][j];
			a[i][0]+=a[i][j];
			a[0][j]+=a[i][j];
		}	
	if(m<n)	
		roteste();
	/*for(int i=0;i<=m;++i)
		for(int j=0;j<=n+2;++j)
		{
			printf("%d ",a[i][j]);
			if(j==n+2)
				printf("\n");
		}*/		
	back(0);
	printf("%lld\n",bestS);
	return 0;
}