Cod sursa(job #7449)

Utilizator dominoMircea Pasoi domino Data 21 ianuarie 2007 15:46:55
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define FIN "elimin.in"
#define FOUT "elimin.out"
#define MAX_N 16
#define MAX_M 8192
#define FOR(i, a, b) for (i = (a); i < (b); i++)

int N, M, R, C, A[MAX_N][MAX_M], stk[MAX_M], sum_col[MAX_M], V[MAX_M], Res;

void bkt(int lv)
{
    int i, t = 0;

    if (lv == R+1)
    {
        FOR (i, 0, M) V[i] = sum_col[i];
        sort(V, V+M);
        t = 0;
        FOR (i, C, M) t += V[i];
        if (Res < t) Res = t;
        return;
    }

    for (stk[lv] = stk[lv-1]+1; stk[lv] < N; stk[lv]++)
    {
        FOR (i, 0, M) sum_col[i] -= A[stk[lv]][i];
        bkt(lv+1);
        FOR (i, 0, M) sum_col[i] += A[stk[lv]][i];
    }
}

int main(void)
{
    int i, j, rev = 0;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d %d %d", &N, &M, &R, &C);
    if (N > M) rev = 1;  
    FOR (i, 0, N) FOR (j, 0, M) scanf("%d", rev ? A[j]+i : A[i]+j);
    if (rev) { swap(N, M); swap(R, C); }

    FOR (i, 0, N) FOR (j, 0, M) sum_col[j] += A[i][j];
    stk[0] = -1;
    bkt(1);

    printf("%d\n", Res);

    return 0;
}