Cod sursa(job #6525)

Utilizator filipbFilip Cristian Buruiana filipb Data 19 ianuarie 2007 22:46:34
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define max(a, b) ((a > b) ? a : b)
#define change(a, b) ((a) ^= (b) ^= (a) ^= (b))

using namespace std;

int M, N, R, C, A[7500][16], S[7500], bst = 0;

int main(void)
{
    int i, j, config, nrb, is_bit[16], s_crt, ch = 0;
    
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);
    
    scanf("%d %d %d %d", &M, &N, &R, &C);
    if (M < N) ch = 1;

    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            if (ch) scanf("%d", &A[j][i]);
            else scanf("%d", &A[i][j]);
    if (ch)
       change(M, N), change(R, C);
    
    for (config = 0; config < (1<<N); config++)
    {   
        memset(is_bit, 0, sizeof(is_bit));
        for (i = 0, nrb = 0; i < N; i++)
            if (config & (1<<i))
               is_bit[i] = 1, nrb++;
        if (nrb != C) continue;
        
        memset(S, 0, sizeof(S));
        for (i = 0; i < M; i++)
            for (j = 0; j < N; j++)
                if (!is_bit[j])
                   S[i] += A[i][j];
        sort(S+0, S+M);
     
        for (s_crt = 0, i = R; i < M; i++)
            s_crt += S[i];
        bst = max(bst, s_crt);              
    }
    
    printf("%d\n", bst);
        
    return 0;
}