Cod sursa(job #515329)

Utilizator hurrycaneBogdan Gaza hurrycane Data 21 decembrie 2010 03:35:42
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define NMAX 7500

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

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

  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;

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

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

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

 

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