Cod sursa(job #1066949)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 25 decembrie 2013 21:17:35
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int NMAX = 7300;
const int MMAX = 20;
int N,M,R,C,i,j,A[NMAX][MMAX],Sol,St[MMAX];
bool viz[MMAX];
void Back(int k)
{
    if(k==C+1)
    {
        int S[7300]; memset(S,0,sizeof(S));
        for(int j=1;j<=M;j++)
            if(!viz[j])
                for(int i=1;i<=N;i++)
                    S[i]+=A[i][j];
        sort(S+1,S+N+1); int Aux=0;
        for(int i=R+1;i<=N;i++) Aux+=S[i];
        Sol=max(Sol,Aux);
    }
    else
    {
        for(int i=St[k-1]+1;i<=M;i++)
            {viz[i]=1; St[k]=i; Back(k+1); viz[i]=0;}
    }
}
int main()
{
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	scanf("%d%d%d%d",&N,&M,&R,&C);
	if(N>M)
	{
	    for(i=1;i<=N;i++)
            for(j=1;j<=M;j++) scanf("%d",&A[i][j]);
	}
	else
	{
	    for(j=1;j<=N;j++)
            for(i=1;i<=M;i++) scanf("%d",&A[i][j]);
        swap(N,M); swap(R,C);
	}
	Back(1); printf("%d\n",Sol);
	return 0;
}