Cod sursa(job #2032360)

Utilizator herbertoHerbert Mohanu herberto Data 4 octombrie 2017 21:02:26
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include<stdio.h>
using namespace std;

int mat[16][3500], auxm[16][3500], f[16], col[3500], v[3500];

void myqsort( int begin, int end, int *v) {
  int aux, b = begin, e = end,
    pivot = v[(begin + end) / 2];

  while ( b <= e ) {
    while ( v[b] < pivot ) b++;
    while ( v[e] > pivot ) e--;
    if ( b <= e ) {
      aux = col[b]; col[b] = col[e]; col[e] = aux;
      b++; e--;
    }
  }
  if ( begin < e ) myqsort( begin, e ,v);
  if ( b < end ) myqsort( b, end, v);
}

int main(){
  FILE*fin=fopen("elimin.in", "r");
  FILE*fout=fopen("elimin.out", "w");
  int n, m, r, c, i, j, aux, smax, max, nr, s, k;
  fscanf(fin, "%d%d%d%d", &n, &m, &r, &c);
  for(i=1; i<=n; i++)
      for(j=1; j<=m; j++)
        fscanf(fin, "%d", &mat[i][j]);
  if(n>m){
//    printf("DA");
    for(i=1; i<=m; i++)
      for(j=1; j<=n; j++){
        auxm[i][j]=mat[j][m-i+1];
//        printf("%d %d %d %d\n", i, j, j, m-i+1);
      }
    aux=n; n=m; m=aux;
    aux=r; r=c; c=aux;

//    printf("%d %d", n, m);
    for(i=1; i<=n; i++)
      for(j=1; j<=m; j++)
        mat[i][j]=auxm[i][j];
  }
  smax=0;
  max=1<<n;
  for(k=0; k<=max-1; k++){
    nr=0;
    for(j=0; j<n; j++)
      if((k&(1<<j))>0){
        nr++;
        f[j+1]=1;
      }
    if(nr==r){
//      printf("DA %d %d %d\n", f[1], f[2], f[3]);
      for(j=1; j<=m; j++)
        for(i=1; i<=n; i++)
          if(f[i]==0)
            col[j]+=mat[i][j];
//      printf("%d %d %d\n\n", col[1], col[2], col[3]);
      myqsort(1, m, col);
      s=0;
      for(j=c+1; j<=m; j++)
        s+=col[j];
      if(s>smax)
        smax=s;
    }
    for(j=1; j<=n; j++){
      f[j]=0;
      col[j]=0;
    }
  }
  fprintf(fout, "%d", smax);
//  for(i=1; i<=n; i++){
//    for(j=1; j<=m; j++)
//        printf("%d ", mat[i][j]);
//    printf("\n");
//  }

  return 0;
}