Cod sursa(job #33574)

Utilizator ionescu_bogdanIonescu Bogdan-Gabriel ionescu_bogdan Data 19 martie 2007 15:15:13
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define nmax 10000

int n,m,r,c,i,j,k,on[20],a[20][nmax],aux,sol,ss[nmax],ssl,n1;

int next()
{
    do
    {
        i=n-1;
        while ((on[i]==1)&&(i>=0))
            on[i]=0,--n1,--i;
        if (i<0)
            return 0;
        on[i]=1,++n1;
    }
    while (n1!=r);
    return 1;
}

int fc(const void *a,const void *b)
{
    return *(int*)b-*(int*)a;
}

int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);

    scanf("%d%d%d%d",&n,&m,&r,&c);
    if (n>m)
    {
        aux=n,n=m,m=aux;
        aux=r,r=c,c=aux;
        for (i=0;i<m;i++)
            for (j=0;j<n;j++)
                scanf("%d",a[j]+i);
    }
    else
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
                scanf("%d",a[i]+j);
    if (r==0)
    {
        memset(ss,0,sizeof(ss));
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
                if (on[i]==0)
                   ss[j]+=a[i][j];
        qsort((void*)ss,m,sizeof(ss[0]),fc);
        ssl=0;
        for (i=0;i<m-c;i++)
            ssl+=ss[i];
        if (sol<ssl)
            sol=ssl;
    }
    while (next())
    {
        memset(ss,0,sizeof(ss));
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
                if (on[i]==0)
                   ss[j]+=a[i][j];
        qsort((void*)ss,m,sizeof(ss[0]),fc);
        ssl=0;
        for (i=0;i<m-c;i++)
            ssl+=ss[i];
        if (sol<ssl)
            sol=ssl;
    }
    printf("%d\n",sol);

    return 0;
}