Cod sursa(job #675031)

Utilizator Cristina94Cristina Ungurean Cristina94 Data 6 februarie 2012 23:39:46
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("elimin.in");
ofstream g("elimin.out");
int n,m,r,c,k, v[100],lin,y[5000][100],a[100][100],stot,b[100][100];

int bun(int j)
{
	for(int i=1;i<j;i++)
		if(v[j]<=v[i])
			return 0;
	return 1;
}

void comb (int i,int n)
{
	lin=0;
	while(i>0&&i<=n)
	{
		v[i]++;
		if(v[i]>n)
			 v[i]=0,i--;
		else
			if(bun(i))
				i++;
		if(i>k)
		{
			lin++;
			for(int j=1;j<=k;j++)
				y[lin][j]=v[j];
			i=k;
		}
	}
}

int main()
{ 
	int i,j,s,l,max=0,el,ok,sum;
	f>>m>>n>>r>>c;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			f>>a[i][j],b[i][j]=a[i][j];//stot+=a[i][j];
	k=n-c;	
	comb(1,n);
	for(i=1;i<=lin;i++)
	{	
		s=0;
		for(j=1;j<=k;j++)
			for(l=1;l<=m;l++)
				s=s+a[l][y[i][j]]; // suma cu coloanele eliminate
		if(max<s)
			max=s, el=i;
	}
	
	for(j=1;j<=n;j++)
	{
		ok=1;
		for(i=1;i<=k;i++)
			if(y[el][i]==j)
				ok=0,i=n+1;
		if(ok==1)
			for(i=1;i<=m;i++)
				a[i][j]=0;
	}
	
	k=m-r;
	//golire v
	for(i=1;i<=100;i++)
		v[i]=0;
	
	comb(1,m);
	max=0;
	for(i=1;i<=lin;i++)
	{	
		s=0;
		for(j=1;j<=k;j++)
			for(l=1;l<=n;l++)
				s=s+a[y[i][j]][l]; // suma cu linii eliminate
		if(max<s)
			max=s, el=i;	
	}
	g<<max<<" "<<el<<'\n';
	for(j=1;j<=m;j++)
	{
		ok=1;
		for(i=1;i<=k;i++)
			if(y[el][i]==j)
				ok=0,i=n+1;
		if(ok==1)
			for(i=1;i<=m;i++)
				a[j][i]=0;
	}
	sum=0;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			sum+=a[i][j];
	
	g<<sum<<'\n';
	return 0;
}