Cod sursa(job #87583)

Utilizator andrei_infoMirestean Andrei andrei_info Data 27 septembrie 2007 21:12:36
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

short int a[15][600];
int suma[600], x[15], N,M,r,c,s,rez;

void citire()
{
    freopen("elimin.in", "r", stdin);
    scanf("%d%d%d%d\n", &M, &N, &r, &c);

    if ( M < 15 )
        for (int i = 0; i< M; i++)
            for (int j=0; j<N; j++)
                scanf("%hd", &a[i][j]);
    else
    {
        swap(r,c);
        for (int j = 0; j<M; j++)
            for (int i = 0; i<N; i++)
                scanf("%hd", &a[i][j]);
        swap(M,N);
    };
    fclose(stdin);
};

void calc()
{

    memset( suma, 0, sizeof(suma));
    for (int i = 0; i < M; i++)
        if (x[i])
            for (int j = 0; j<N; j++)
                suma[j]+=a[i][j];
    sort(suma, suma+N);
    int rr =0;
    for (int i=N-1; i>=c; i--)
        rr+=suma[i];
    if (rr > rez) rez = rr;
};


void back( int k)
{
    if ( k == M )
    {
        if ( s == r)
            calc();
    }
    else

        for (short int i = 0; i<=1; i++)
        {
            x[k] = i;
            if (!i) s++;
            if (s <= r)
                back(k+1);
            if (!i) s--;
        };
};

int main()
{
    citire();
    back(0);

    freopen("elimin.out", "w", stdout);
    printf("%d", rez);
    fclose(stdout);

    return 0;
};