Cod sursa(job #1061905)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 20 decembrie 2013 14:07:41
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.05 kb
#include<fstream>
#include<algorithm>
#include<cstdio>
#define LG 2500000
using namespace std;
int n,m,R,C,Matrix[610][610],maxSolution,columnSum[7300];
int Value[20],v[7300];


ifstream in("elimin.in");
ofstream out("elimin.out");

void Verif()
{
	int i,j,now=0;
	for(j=1;j<=m;j++)
	{
		v[j]=columnSum[j];
		for(i=1;i<=R;i++)
			v[j]-=Matrix[Value[i]][j];
	}
	nth_element(v+1,v+C,v+m+1);
	for(i=C+1;i<=m;i++)
		now+=v[i];
	maxSolution=max(maxSolution,now);
}

void Back(int pas)
{
	if(pas==R+1)
		Verif();
	else
	{
		int i;
		for(i=Value[pas-1]+1;i<=n-R+pas;i++)
		{
			Value[pas]=i;
			Back(pas+1);
		}
	}
}

int main()
{
	int i,j;
	in >> n >> m >> R >> C;
	if(n<=m)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
			    in >> Matrix[i][j];
				columnSum[j]+=Matrix[i][j];
			}
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
			    in >> Matrix[j][i];
				columnSum[i]+=Matrix[j][i];
			}
		}
		swap(n,m);
		swap(R,C);
	}

	Back(1);
    out << maxSolution;
	return 0;
}