Cod sursa(job #1002581)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 28 septembrie 2013 11:02:07
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n,m,R,C,mat[500][500],sum,sol,sumC[500];
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;i++)
		{
			lin[pas]=i;
			Back(pas+1);
		}
	}
}

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