Cod sursa(job #695882)

Utilizator vlad2901Vlad Berindei vlad2901 Data 28 februarie 2012 15:21:19
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
#include <algorithm>

#define MMAX 8192
#define NMAX 128

using namespace std;

short a[MMAX][NMAX];
int cols[NMAX], rows[MMAX], sol;
int N, M, R, C;

int check(int k)
{
    int nr = 0;
    for(int i=0;i<=k;++i)
    {
        nr += cols[i];
    }

    if(nr > C)
    {
        return 0;
    }

    if(nr + N - k - 1 < C)
    {
        return 0;
    }
    return 1;
}

void update()
{
    for(int i=0;i<M;++i) rows[i] = 0;

    for(int j=0;j<N;++j)
    {
        if(!cols[j])
        {
            for(int i=0;i<M;++i)
            {
                rows[i] += a[i][j];
            }
        }
    }
    sort(rows, rows+M);

    int sum = 0;

    for(int i=M-1;i>=R;--i)
    {
        sum += rows[i];
    }

    if(sum > sol)
    {
        sol = sum;
    }


}

void back(int k)
{
    if(k == N)
    {
        update();
    }
    else
    {
        for(int i=0;i<2;++i)
        {
            cols[k] = i;
            if(check(k))
            {
                back(k+1);
            }
        }
    }
}


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

    scanf("%d %d %d %d", &M, &N, &R, &C);

    if(M >= N)
    {
        for(int i=0;i<M;++i)
            for(int j=0;j<N;++j)
                scanf("%d", &a[i][j]);
    }
    else
    {
        for(int i=0;i<M;++i)
            for(int j=0;j<N;++j)
                scanf("%d", &a[j][i]);
        swap(N,M);
        swap(R,C);
    }

    back(0);

    printf("%d", sol);

    return 0;
}