Cod sursa(job #546145)

Utilizator noemirkNoemi Noemi noemirk Data 4 martie 2011 15:16:16
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <vector>
#include <fstream>
using namespace std;
ifstream fi("elimin.in");
ofstream fo("elimin.out");
int n,m,i,j,a;
int R,C;
vector <int> V[7300];
int S[100];
int OK[100];
int SC[10000],SL[10000];
int rez;

void gl(int k)
{
    int i,j,suma;
	vector <int> :: iterator it;
    if (k==R)
    {
		for (i=1;i<=n;i++)
			OK[i]=1;
        for (i=1;i<=R;i++)
			OK[S[i]]=0;
		for (i=1;i<=m;i++)
			SC[i]=0;
        for (i=1;i<=n;i++)
			if (OK[i]==1)
			{
				j=0;
				for (it=V[i].begin();it!=V[i].end();it++)
				{
					j++;
					SC[j]+=(*it);
				}
			}
		sort(SC+1,SC+m+1);
		suma=0;
		for (i=C+1;i<=m;i++)
			suma+=SC[i];
		if (suma>rez)
			rez=suma;
    }
    else
        for (i=S[k]+1;i<=n;i++)
        {
            S[k+1]=i;
			gl(k+1);
        }
}

void gc(int k)
{
    int i,j,suma;
	vector <int> :: iterator it;
    if (k==C)
    {
		for (i=1;i<=m;i++)
			OK[i]=1;
        for (i=1;i<=C;i++)
			OK[S[i]]=0;
		for (i=1;i<=m;i++)
			SL[i]=0;
        for (i=1;i<=m;i++)
			if (OK[i]==1)
			{
				j=0;
				for (it=V[i].begin();it!=V[i].end();it++)
				{
					j++;
					SL[j]+=(*it);
				}
			}
		sort(SL+1,SL+m+1);
		suma=0;
		for (i=R+1;i<=n;i++)
			suma+=SL[i];
		if (suma>rez)
			rez=suma;
    }
    else
        for (i=S[k]+1;i<=m;i++)
        {
            S[k+1]=i;
			gc(k+1);
        }
}

int main()
{
	fi>>n>>m>>R>>C;
	if (n<=m)
	{
		for (i=1;i<=n;i++)
			for (j=1;j<=m;j++)
			{
				fi>>a;
				V[i].push_back(a);
			}
		rez=-1;
		gl(0);
		fo<<rez;
	}
	else
	{
		for (i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				fi>>a;
				V[j].push_back(a);
			}
		rez=-1;
		gc(0);
		fo<<rez;
	}
	fi.close();
	fo.close();
	return 0;
}