Cod sursa(job #1843009)

Utilizator pibogaBogdan piboga Data 7 ianuarie 2017 22:58:51
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <algorithm>

using namespace std;

/*
ifstream fin ("elimin.in");
ofstream fout("elimin.out");*/

int n,m,r,c,N,M,u,k,mx,i,j,nr,s,ss;
int mk[7500],t[7500],a[20][7500],bt[32010];

//a[15][7294]

int main()
{
  //  fin >> n >> m >> r >> c ;

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

    scanf("%i",&n);
    scanf("%i",&m);
    scanf("%i",&r);
    scanf("%i",&c);

    if (n>m)
    {
        for (j=1;j<=n;++j)
        {
            for (i=1;i<=m;++i)
            {
                    scanf("%i",&a[i][j]);
            }
        }

        swap (n,m);
        swap (r,c);
    }

    else

    {
        for (i=1;i<=n;++i)
        {
            for (j=1;j<=m;++j)
            {
                    scanf("%i",&a[i][j]);
            }
        }


    }

    nr=(1<<n)-1;

    for (k=1;k<=nr;++k)
    {
        u=0;

        if (2 * k <= nr) bt[2*k] = bt[k];
        if (2 * k + 1 <= nr) bt[2*k+1] = bt[k]+1;
    }

    for (k=1;k<=nr;++k)
    {

        ss=0;
        u=bt[k]+1;

        if (u==r)
        {
            for (i=1;i<=n;++i)
            {
                if (k>>(i-1)&1)
                {
                    mk[i]=k;
                }
            }


            for (j=1;j<=m;++j)
            {
                s=0;

                for (i=1;i<=n;++i)
                    if (mk[i]!=k)
                        s+=a[i][j];

                t[j]=s;

            }

            sort (t+1,t+m+1);

            for (j=m;j>=c+1;--j)
            {
                ss+=t[j];
            }

            if (ss>mx) mx=ss;


        }
    }




  //  fout <<mx;

    printf("%i",mx);

    return 0;
}