Cod sursa(job #1466414)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 29 iulie 2015 02:41:22
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <ctype.h>

#define MAX_N 17
#define MAX_M 7294
#define NIL -1
#define BUFFSIZE (1 << 15)

short a[MAX_M][MAX_N];

bool v[MAX_N];

int sum[MAX_M];

char buffer[BUFFSIZE];
int pos = BUFFSIZE;

inline char get(FILE *f) {
  if (pos == BUFFSIZE) {
    fread(buffer, 1, BUFFSIZE, f);
    pos = 0;
  }
  return buffer[pos++];
}

template <class T>
inline void read(T *q, FILE *f) {
  char c;
  do {
    c = get(f);
  } while (!isdigit(c));
  *q = 0;
  do {
    *q = (*q << 1) + (*q << 3) + (c - '0');
    c = get(f);
  } while (isdigit(c));
}

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

  read(&n, f);
  read(&m, f);
  read(&r, f);
  read(&c, f);

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

  for (int i = r; i < n; i++) {
    v[i] = 1;
  }
  ans = 0;
  do {
    for (register int i = 0; i < m; ++i) {
      sum[i] = 0;
      for (register int j = 0; j < n; ++j) {
        sum[i] += (a[i][j] & -v[j]);
      }
    }
    std::sort(sum, sum + m, std::greater<int>());
    q = 0;
    for (register int i = 0; i + c < m; ++i) {
      q += sum[i];
    }
    if (q > ans) {
      ans = q;
    }
  } while (std::next_permutation(v, v + n));

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