Cod sursa(job #1946168)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 29 martie 2017 22:39:00
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int a[20][8000],st[20],fv[20],cost[8000],wurk[8000];
int n,m,r,c,mx;
void bkt(int poz)
{
    int i,j;
    if(poz==r)
    {
        int s=0;
        for(i=1;i<=m;i++)
        {
            wurk[i]=cost[i];
            for(j=1;j<=r;j++)
                wurk[i]-=a[st[j]][i];
        }
        sort(&wurk[1],&wurk[m+1]);
        for(i=c+1;i<=m;i++)
            s+=wurk[i];
        if(s>mx)
            mx=s;
    }
    else
    {
        for(i=st[poz]+1;i<=n;i++)
            if(!fv[i])
        {
            fv[i]=1;
            st[poz+1]=i;
            bkt(poz+1);
            fv[i]=0;
        }
    }
}
int main()
{
    int i,j;
    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(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[j][i]);
        i=m;
        m=n;
        n=i;
        i=r;
        r=c;
        c=i;
    }
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            cost[i]+=a[j][i];
    bkt(0);
    printf("%d ",mx);
    return 0;
}