Cod sursa(job #736765)

Utilizator robertpoeRobert Poenaru robertpoe Data 19 aprilie 2012 11:18:51
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("elimin.in");
ofstream g("elimin.out");
int n,aux,m,i,c,r,j,maxi,x[20],a[700][20];
void verif()
{
	int s=0,j,i,sum[1000];
	for(i=1;i<=m;++i)
		sum[i]=a[i][0];
	for(i=1;i<=c;++i)
		for(j=1;j<=m;++j)
			sum[j]=sum[j]-a[j][x[i]];
	sort(sum+1,sum+1+m);
	for(i=r+1;i<=m;++i)
		s=s+sum[i];
	if(s>maxi)
		maxi=s;
}
int main()
{
	f>>m>>n>>r>>c;
	if(m<n)
	{
		for(i=1;i<=m;++i)
			for(j=1;j<=n;++j)
				f>>a[j][m-i+1];
			aux=r;
			r=c;
			c=aux;
			aux=n;
			n=m;
			m=aux;
	}
	else
	for(i=1;i<=m;++i)
		for(j=1;j<=n;++j)
			f>>a[i][j];
	for(i=1;i<=m;++i)
		for(j=1;j<=n;++j)
			a[0][j]=a[0][j]+a[i][j],a[i][0]=a[i][0]+a[i][j];
	for(i=1;i<=c;++i)
		x[i]=i;
	verif();
	while(1)
	{
		i=c;
		while(x[i]==n-c+i)
			--i;
		if(i==0)
			break;
		else
		{
			++x[i];
			for(j=i+1;j<=c;++j)
				x[j]=x[j-1]+1;
			verif();
		}
	}
	g<<maxi<<'\n';
	return 0;
}