Cod sursa(job #873306)

Utilizator timicsIoana Tamas timics Data 7 februarie 2013 01:30:01
Problema Elimin Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int M,R,C,N,MA,NR,x[600][600],b=0,s[600];
char a[20],v[20],bla[20];
void make1()
{
    int ma=0;
    for(int i=1;i<=M-R;++i)
        bla[a[i]]=1;
    for(int j=1;j<=N;++j)
    {
        for(int i=1;i<=M;++i)
            if(bla[i]==1)
            {
                s[j]=s[j]+x[i][j];
            }
    }
    nth_element(s+1,s+C,s+N+1);
    for(int i=C+1;i<=N;++i)
        ma=ma+s[i];
    printf("%d\n",ma);
    for(int j=1;j<=N;++j)
        s[j]=0;
    for(int i=1;i<=M;++i)
        bla[i]=0;
    if(ma>b)
        b=ma;
}

void make2()
{
    int ma=0;
    for(int i=1;i<=N-C;++i)
        bla[a[i]]=1;
    for(int j=1;j<=M;++j)
    {
        for(int i=1;i<=N;++i)
            if(bla[i]==1)
            {
                s[j]=s[j]+x[j][i];
            }
    }
    nth_element(s+1,s+R,s+M+1);
    for(int i=R+1;i<=M;++i)
        ma=ma+s[i];
    for(int j=1;j<=M;++j)
        s[j]=0;
    for(int i=1;i<=N;++i)
        bla[i]=0;
    if(ma>b)
        b=ma;
}
void backy(int k)
{
    if(k==NR+1)
    {
        if(R<C)
            make1();
        else
            make2();
    }
    else
    {
        for(int i=1;i<=MA;++i)
            if((v[i]==0)&&(i>a[k-1]))
            {
                a[k]=i;
                v[i]=1;
                backy(k+1);
                v[i]=0;
            }
    }
}
int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    scanf("%d %d %d %d",&M,&N,&R,&C);
    for(int i=1;i<=M;++i)
        for(int j=1;j<=N;++j)
            scanf("%d",&x[i][j]);
    if(R<C)
    {
        MA=M;
        NR=M-R;
    }
    else
    {
        MA=N;
        NR=N-C;
    }
    backy(1);
    printf("%d",b);
    return 0;
}