Cod sursa(job #14108)

Utilizator victorsbVictor Rusu victorsb Data 8 februarie 2007 11:50:08
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;

#define Mmax 20
#define Nmax 8000

int m, n, r, c, k, sol;
int mat[Mmax][Nmax];
int lin[Mmax], s[Nmax];

void citire()
{
    int i, j, caz = 0;
    scanf("%d %d %d %d\n", &m, &n, &r, &c);
    if (n < m)
        caz = 1;
    for (i=1; i<=m; ++i)
        for (j=1; j<=n; ++j)
            if (!caz)
                scanf("%d", &mat[i][j]);
            else
                scanf("%d", &mat[j][i]);
    if (caz)
    {
        swap(n, m);
        swap(r, c);
    }
}

void verif()
{
    int i, j, suma = 0;
    memset(s, 0, sizeof(s));
    for (i=1; i<=m; ++i)
        if (!lin[i])
            for (j=1; j<=n; ++j)
                s[j] += mat[i][j];
    sort(s+1, s+n+1);
    reverse(s+1, s+n+1);
    /*
    for (i=1; i<=m; ++i)
        printf("%d ", lin[i]);
    printf("\n");
    for (i=1; i<=n; ++i)
        printf("%d ", s[i]);
    printf("\n\n");
    */
    for (i=1; i<=n - c; ++i)
        suma += s[i];
    if (suma > sol)
        sol = suma;
}

void back(int p)
{
    if (p > m)
        return;
    // nu iau coloana p
    lin[p] = 0;
    back(p + 1);
    
    // iau coloana p
    lin[p] = 1;
    --k;
    if (!k)
        verif();
    else
        back(p + 1);
    ++k;
    lin[p] = 0;
}

void solve()
{
    int i, j;
    k = r;
    /*
    for (i=1; i<=m; ++i)
    {
        for (j=1; j<=n; ++j)
            printf("%d ", mat[i][j]);
        printf("\n");
    }
    */
    back(1);
    printf("%d\n", sol);
}

int main()
{
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);
    citire();
    solve();
    return 0;
}