Cod sursa(job #872400)

Utilizator MKLOLDragos Ristache MKLOL Data 6 februarie 2013 00:36:31
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int v[101];
vector<vector<int> >  a;
vector<vector<int> > m;
int N,M,R,C,NR,MA,ok,rez=-12345;
int l[1010];


inline void make()
{
    int ret=0;
    for(int i=1;i<=max(N,M);++i)
        l[i]=0;

  //  printf("\n");
    if(ok==1)
    {
        for(int i=1;i<=N;++i)
        {
            for(int j=1;j<=M;++j)
            {
                l[j]+=m[i][j];
            }
        }
        sort(l+1,l+M+1);
        for(int i=C+1;i<=M;++i)
        {
            ret+=l[i];
        }
    }
    else
    {
        for(int i=1;i<=N;++i)
        {
            for(int j=1;j<=M;++j)
            {
                l[i]+=m[i][j];
            }
        }
        sort(l+1,l+N+1);
        for(int i=R+1;i<=N;++i)
        {
            ret+=l[i];
        }

    }
/*  for(int i=1;i<=N;++i)
        {
            for(int j=1;j<=M;++j)
            {
            printf("%d ",m[i][j]);
            }
        printf("\n");
        }
        printf("\n\n");
        for(int i=1;i<=M;++i)
            printf("%d ",l[i]);
        printf("\n\n");*/
    if(ret>rez)
        rez=ret;
        //printf("%d \n",ret);
}


void back(int k)
{
    if(k==NR+1)
    {
    make();
    }
    else
    {
        for(int i=v[k-1]+1;i<=MA;++i)
        {

            v[k]=i;
            int x=v[k];
            if(NR+1-k<=v[k])
            {
            if(ok==1)
            {
                for(int i=1;i<=M;++i)
                {
                    m[x][i]=0;
                }
            }
            else
            {
                for(int i=1;i<=N;++i)
                {
                    m[i][x]=0;
                }
            }
            back(k+1);
            if(ok==1)
            {
                for(int i=1;i<=M;++i)
                {
                    m[x][i]=a[x][i];
                }
            }
            else
            {
                for(int i=1;i<=N;++i)
                {
                    m[i][x]=a[i][x];
                }
            }
            v[k]=0;
            }
        }
    }
}

int main()
{
freopen("elimin.in","r",stdin);
freopen("elimin.out","w",stdout);
scanf("%d%d%d%d",&N,&M,&R,&C);
    a.resize(N+4);
    m.resize(N+4);
    for(int i=0;i<N+3;++i)
    {
        a[i].resize(M+4);
        m[i].resize(M+4);
    }
    if(N<M)
    {
    ok=1;
    MA=N;
    NR=R;
    }
    else
    {
    ok=2;
    MA=M;
    NR=C;
    }
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
        {
        scanf("%d",&a[i][j]);
        }
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
        {
            m[i][j]=a[i][j];
        }
    back(1);
    printf("%d",rez);
    return 0;
}