Cod sursa(job #486334)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 21 septembrie 2010 10:12:58
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<cstdio>
#include<algorithm>
#define N 1<<12
using namespace std;
int maxs,n,m,r,c,nr1,v[N],a[N][N],s[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;
    for(int i=0;i<N;i++)
        s[i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[j]+=a[i][j]*(1-v[i]);
    sort(s+1,s+m+1);
    for(int j=c+1;j<=m;j++)
        st+=s[j];
    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;
    for(int i=0;i<N;i++)
        s[i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i]+=a[i][j]*(1-v[j]);
    sort(s+1,s+n+1);
    for(int i=r+1;i<=n;i++)
        st+=s[i];
    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;
}