Cod sursa(job #976217)

Utilizator dariusdariusMarian Darius dariusdarius Data 22 iulie 2013 19:33:56
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
int a[20][7300];
int sum[7300];
int one_bits(int x)
{
    if(x==0) return 0;
    return one_bits(x&(x-1))+1;
}
int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    int ans,fin=-1,n,m,r,c;
    bool flag=false;
    scanf("%d%d%d%d",&n,&m,&r,&c);
    if(n>m) swap(r,c),flag=true;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(flag)
                scanf("%d",&a[j][n+1-i]);
            else
                scanf("%d",&a[i][j]);
    if(flag) swap(n,m);
    for(int V=0;V<(1<<n);V++)
    {
        if(one_bits(V)!=r) continue;
        for(int j=1;j<=m;j++)
            sum[j]=0;
        for(int i=1;i<=n;i++)
            if((V&(1<<(i-1)))==0)
                for(int j=1;j<=m;j++)
                    sum[j]+=a[i][j];
        sort(sum+1,sum+m+1);
        ans=0;
        for(int i=c+1;i<=m;i++)
            ans+=sum[i];
        fin=max(fin,ans);
    }
    printf("%d\n",fin);
    return 0;
}