Cod sursa(job #189062)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 11 mai 2008 19:15:18
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 522
#define N 20
using namespace std;
long long bestS,Suma;
int v[Nmax];
int m,n,c,r;
int a[Nmax][Nmax];
int sol[N];
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);
	if(m<n)
	{  
        int aux;
		aux=r; r=c; c=aux; 
		for(int i=1;i<=m;++i)
			for(int j=1;j<=n;++j)
			{
				scanf("%d", &a[j][m+1-i]);
				Suma+=a[j][m+1-i];
				a[j][0]+=a[j][m+1-i];
				a[0][m+1-i]+=a[j][m+1-i];
			}	
		aux=n; n=m; m=aux;  	
    }  
    else
	{  
        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];
			}	
    }  
	/*for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
		{
			printf("%d ",a[i][j]);
			if(j==n)
				printf("\n");
		}*/
	back(0);
	printf("%lld\n",bestS);
	return 0;
}