Cod sursa(job #1466397)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 29 iulie 2015 01:51:24
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <assert.h>

#define MAX_N 63
#define MAX_M 7294
#define NIL -1

short a[MAX_M][MAX_N];
int sum[MAX_M];
short next[MAX_N];

inline int buildList(const unsigned long long &p, const int &n) {
  int i;
  int prev;

  memset(next, NIL, sizeof(next));
  i = 0;
  while (p & (1ULL << i)) {
    i++;
  }
  prev = i;
  i++;
  for (; i < n; i++) {
    if (!(p & (1ULL << i))) {
      next[i] = prev;
      prev = i;
    }
  }
  return prev;
}

/*
inline void printBits(const unsigned long long &p) {
  for (int i = 0; i < 64; i++) {
    if (p & (1ULL << i)) {
      putchar('1');
    } else {
      putchar('0');
    }
  }
  putchar('\n');
} */

int main(void) {
  FILE *f = fopen("elimin.in", "r");
  int n, m, r, c;
  int ans, q;
  unsigned long long currentPerm, nextPerm, t;

  fscanf(f, "%d%d%d%d", &n, &m, &r, &c);

  if (n <= m) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        fscanf(f, "%hd", &a[j][i]);
      }
    }
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        fscanf(f, "%hd", &a[i][j]);
      }
    }
    std::swap(n, m);
    std::swap(r, c);
  }
  fclose(f);

  nextPerm = (1ULL << r) - 1;
  ans = 0;
  do {
    currentPerm = nextPerm;
    q = buildList(currentPerm, n);
    for (int i = 0; i < m; i++) {
      sum[i] = 0;
      for (int j = q; j != NIL; j = next[j]) {
        sum[i] += a[i][j];
      }
    }
    std::make_heap(sum, sum + m);
    q = 0;
    for (int i = 0; i + c < m; i++) {
      q += sum[0];
      std::pop_heap(sum, sum + m - i);
    }
    if (q > ans) {
      ans = q;
    }
    t = (currentPerm | (currentPerm - 1)) + 1;
    nextPerm = t | ((((t & -t) / (currentPerm & -currentPerm)) >> 1ULL) - 1);
  } while (nextPerm < (1ULL << n));

  f = fopen("elimin.out", "w");
  fprintf(f, "%d\n", ans);
  fclose(f);
  return 0;
}