Cod sursa(job #8016)

Utilizator astronomyAirinei Adrian astronomy Data 23 ianuarie 2007 17:03:17
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define max(a,b) ((a) > (b) ? (a) : (b))

int N, M, R, C, sum;
int A[1<<4][1<<12], V[1<<12], Col[1<<12];
int res;

int x[16];

void bkt(int k)
{
    int i, r, j, val;
    
    if(k == N+1)
    {
        for(r = 0, i = 1; i <= N; i++)
            r += x[i];

        if(r != R)
            return ;
            
        val = sum;
        for(j = 1; j <= M; j++)
            V[j] = Col[j];
            
        for(i = 1; i <= N; i++)
         if(x[i])
          for(j = 1; j <= M; j++)
            V[j] -= A[i][j], val -= A[i][j];

        sort(V+1, V+M+1);

        for(i = 1; i <= C; i++)
            val -= V[i];

        res = max(val, res);
    }
    else
        x[k] = 0, bkt(k+1), x[k] = 1, bkt(k+1);
}

void read_data(void)
{
    int i, j, x;
    
    scanf("%d %d %d %d\n", &N, &M, &R, &C);

    for(i = 1; i <= N; i++)
     for(j = 1; j <= M; j++)
     {
        scanf("%d\n", &x), sum += x;
        if(N > M)
            A[M-j+1][i] = x, Col[i] += x;
        else
            A[i][j] = x, Col[j] += x;
     }

    if(N > M)
        N ^= M, M ^= N, N ^= M, R ^= C, C ^= R, R ^= C;
}

void write_data(void)
{
    printf("%d\n", res);
}

int main(void)
{
    freopen("elimin.in", "rt", stdin);
    freopen("elimin.out", "wt", stdout);

    read_data();
    bkt(1);
    write_data();

    return 0;
}