Cod sursa(job #486330)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 21 septembrie 2010 10:04:31
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<cstdio>
#define N 1<<12
int maxs,n,m,r,c,nr1,v[N],a[N][N],s[N],used[N];
void read()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&r,&c);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
}
void makesuml()
{
    int st=0,nrt=0;
    for(int i=0;i<N;i++)
        s[i]=used[i]=0;
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
            s[j]+=a[i][j]*(1-v[i]);
    do
    {
        nrt++;
        int min=1<<30,pmin=0;
        for(int i=1;i<=n;i++)
            if(s[i]<min && !used[i])
                min=s[i],pmin=i;
        used[pmin]=1;
        st-=min;
    }
    while(nrt<c);
    if(st>maxs)
        maxs=st;
}
void backl(int poz)
{
    if(poz==n+1)
    {
        if(nr1==r)
            makesuml();
        return;
    }
    v[poz]=0;
    backl(poz+1);
    if(nr1<r)
    {
        v[poz]=1;
        nr1++;
        backl(poz+1);
        nr1--;
    }
}
void makesumc()
{
    int st=0,nrt=0;
    for(int i=0;i<N;i++)
        s[i]=used[i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i]+=a[i][j]*(1-v[j]);
    for(int i=1;i<=n;i++)
        st+=s[i];
    do
    {
        nrt++;
        int min=1<<30,pmin=0;
        for(int i=1;i<=n;i++)
            if(s[i]<min && !used[i])
                min=s[i],pmin=i;
        used[pmin]=1;
        st-=min;
    }
    while(nrt<r);
    if(st>maxs)
        maxs=st;
}
void backc(int poz)
{
    if(poz==m+1)
    {
        if(nr1==c)
            makesumc();
        return;
    }
    v[poz]=0;
    backc(poz+1);
    if(nr1<c)
    {
        v[poz]=1;
        nr1++;
        backc(poz+1);
        nr1--;
    }
}
void solve()
{
    maxs=-1;
    if(n<m)
        backl(1);
    else
        backc(1);
    printf("%d",maxs);
}
int main()
{
    read();
    solve();
    return 0;
}