Cod sursa(job #1002588)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 28 septembrie 2013 11:07:25
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n,m,R,C,mat[610][610],sum,sol,sumC[7300];
int lin[20],v[7300];

inline void Verif()
{
	int i,j,elim=0;
	for(i=1;i<=R;i++)
		for(j=1;j<=m;j++)
			elim+=mat[lin[i]][j];
	for(j=1;j<=m;j++)
	{
		v[j]=sumC[j];
		for(i=1;i<=R;i++)
			v[j]-=mat[lin[i]][j];
	}
	sort(v+1,v+m+1);
	for(i=1;i<=C;i++)
		elim+=v[i];
	sol=max(sol,sum-elim);
}

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

int main()
{
	int i,j;
	ifstream fin("elimin.in");
	fin>>n>>m>>R>>C;
	if(n<=m)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				fin>>mat[i][j];
				sum+=mat[i][j];
				sumC[j]+=mat[i][j];
			}
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				fin>>mat[j][i];
				sum+=mat[i][j];
				sumC[j]+=mat[i][j];
			}
		}
		swap(n,m);
		swap(R,C);
	}
	fin.close();
	
	Back(1);
	
	ofstream fout("elimin.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}