Cod sursa(job #129163)

Utilizator pishtymatei silviu pishty Data 28 ianuarie 2008 18:24:33
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 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;   
}   
#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;
}