Cod sursa(job #488702)

Utilizator bog29Antohi Bogdan bog29 Data 29 septembrie 2010 19:14:15
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<fstream>
#include<algorithm>
#define dmax 560
using namespace std;
ifstream in("elimin.in");
ofstream out("elimin.out");

int n,m,mat[dmax][dmax],x,y,cmb[dmax],scol[dmax],smin,st,mx;
bool t[dmax];

void bkt(int k)
{	int i,j;
	if(k==x+1)
	{	for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
			{	if(!t[j])
					scol[i]+=mat[j][i];
				else smin+=mat[j][i];
			}	
		
		sort(scol+1,scol+m+1);
		
		for(i=1;i<=y;i++)	
			smin+=scol[i];
		
		if(st-smin > mx)
			mx=st-smin;
	
		for(i=1;i<=m;i++)
			scol[i]=0;
		smin=0;
	}	
	else
	{	for(i=cmb[k-1]+1;i<=n;i++)
		{	cmb[k]=i;
			t[i]=1;
			bkt(k+1);
			t[i]=0;
		}	
	}
}	

int main()
{	int i,j,t;
	in>>n>>m>>x>>y;
	if(n <= m)
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{	in>>mat[i][j];
				st+=mat[i][j];
			}	
	else
	{	for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{	in>>mat[j][i];
				st+=mat[j][i];
			}	
		t=m,m=n,n=t;
		t=y,y=x,x=t;	
	}	
	in.close();
	
	bkt(1);
	
	out<<mx;
	
	out.close();
	return 0;
}