Cod sursa(job #515320)

Utilizator hurrycaneBogdan Gaza hurrycane Data 21 decembrie 2010 02:59:23
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define NMAX 100

int A[NMAX][NMAX];
int bit_array[NMAX];
int rows[NMAX];

int main(){
  int N,M,R,C;
  int swp,i,j;
  int aux;
  int nr_bits;
  int t;

  int total = 0;
  int partial = 0;

  freopen("elimin.in","r",stdin);
  freopen("elimin.out","w",stdout);

  scanf("%d %d %d %d",&M,&N,&R,&C);

  /* generate the comb for N or M - which is the smallest */
  if(M<N) swp = 1;

  if(swp != 1){
    aux = M;
    M = N;
    N = aux;

    aux = R;
    R = C;
    C = aux;
  }

  for(i=0;i<M;i++)
    for(j=0;j<N;j++)
      if(swp == 1)
        scanf("%d",&A[i][j]);
      else
        scanf("%d",&A[j][i]);

  aux = 1 << N;
  /* loop through all posibilities of having C columns from N */
  for(i=0;i<aux;i++){
    memset(bit_array,0,sizeof(bit_array));
    /* check all bites */
    nr_bits = 0;
    for(j=0;j<N;j++){
      if(i & (1<<j)){
        bit_array[j] = 1;
        nr_bits++;
      }
    }

    if(nr_bits != C) continue;

    memset(rows,0,sizeof(rows));

    for(t = 0; t < M; t++){
      for(j = 0 ; j < N; j++){
        if(bit_array[j] != 1){
          rows[t] += A[t][j];
        }
      }
    }

    std::sort(rows,rows+M);
    /* last M-R columns */
    partial = 0;
    for(t=R;t<M;t++){
      partial += rows[t];
    }
    if(total<partial) total = partial;
  }
  printf("%d",total);



  return 0;
}