Cod sursa(job #1068777)

Utilizator Teodor94Teodor Plop Teodor94 Data 28 decembrie 2013 18:54:58
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.22 kb
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=555;
const int M=20;

int a[N][N],n,m,r,c,sol[M],s[N],s2[N],best;

void read()
{
    scanf("%d%d%d%d",&n,&m,&r,&c);
    int i,j;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    if (n<m)
    {
        for (i=1;i<=n;++i)
            for (j=1;j<=m;++j)
                if (j>i)
                    swap(a[i][j],a[j][i]);
        swap(n,m);
        swap(r,c);
    }
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            s[i]+=a[i][j];
}

void solve()
{
    int i,j,sum=0;
    memcpy(s2,s,sizeof(s));
    for (i=1;i<=c;++i)
        for (j=1;j<=n;++j)
            s2[j]-=a[j][sol[i]];
    //sort(s2+1,s2+n+1);
    nth_element(s2+1,s2+1+r,s2+1+n);
    for (i=r+1;i<=n;++i)
        sum+=s2[i];
    if (sum>best)
        best=sum;
}

void back(int k)
{
    if (k==c+1)
    {
        solve();
        return;
    }
    for (int i=sol[k-1]+1;i<=m;++i)
    {
        sol[k]=i;
        back(k+1);
    }
}

int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    read();
    back(1);
    printf("%d\n",best);
    return 0;
}