1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <stdlib.h>
#include <string.h>
//---===---
#include <stdio.h>
#include <unistd.h>

typedef unsigned int uint;

char buf_in[4096000];
int buf_in_head = 0;
int buf_in_tail = 0;

static int getChar(void) {
  while (buf_in_head == buf_in_tail) {
    int rv = read(0, buf_in, sizeof(buf_in));
    if (rv > 0) {
      buf_in_head = 0;
      buf_in_tail = rv;
      break;
    };
    if (rv == 0) return EOF;
  }
  return buf_in[buf_in_head++];
}

// only 1 call is safe, and only if previously getChar() had been called.
static void ungetChar(void) {
  --buf_in_head;
}

static uint getUInt() {
  uint v;
  int c;
  for (;;) {
    c = getChar();
    if (c < '0') continue;
    if (c > '9') continue;
    v = c - '0';
    break;
  };
  for (;;) {
    c = getChar();
    if (c < '0') break;
    if (c > '9') break;
    v *= 10;
    v += c - '0';
  };
  ungetChar();
  return v;
}
//---===---

#define C24 24
uint a[C24]; // przedmioty
uint c[100]; // plecaki

uint T[1 << C24]; // 64MB, dynamika tu sie dzieje

int cmp(const uint * x, const uint * y) {
  if (*x < *y) return -1;
  if (*x > *y) return +1;
  return 0;
}

int void_incr_cmp(const void * x, const void * y) {
  return cmp((const uint*)x, (const uint*)y);
}

int void_decr_cmp(const void * x, const void * y) {
  return -cmp((const uint*)x, (const uint*)y);
}

int main (void) {
  int n, m, tsize;
  int i, j, k, p;

  // przedmioty: 1 <= n <= 24
  n = getUInt();
  // paczki: 1 <= m <= 100
  m = getUInt();

  tsize = 1 << n;

  for (i = 0; i < n; ++i) a[i] = getUInt(); // 1 <= a[i] <= 100,000,000
  for (i = 0; i < m; ++i) c[i] = getUInt(); // 1 <= c[i] <= 100,000,000

  qsort(a, n, sizeof(a[0]), void_incr_cmp); // przedmioty rosnaca
  qsort(c, m, sizeof(c[0]), void_decr_cmp); // paczki malejaco

  // zatrzymujemy n najwiekszych paczek
  if (m > n) m = n;

  // 1 <= {paczki} m <= {przedmioty} n <= 24

//for (i = 0; i < n; ++i) printf("%d ", a[i]); putchar('\n'); // low to high
//for (i = 0; i < m; ++i) printf("%d ", c[i]); putchar('\n'); // high to low

// must: INF > c[p] >= c[0] >= 10**8
// 0x06060606 == 101058054
// #define INF (100000000 + 1)

  memset(T, 0xFF, sizeof(T[0]) * tsize); // INF
  T[0] = 0; // for all p

  for (p = 0; p < m; ++p) {
    uint limit = c[p];
    for (i = 0; i < tsize; ++i) {
      uint v = T[i];
      if (v > limit) continue;
      T[i] = 0;

      for (j = 0, k = 1; j < n; ++j, k <<= 1) {
        if (i & k) continue;
        uint w = v + a[j];
        if (w > limit) break;
        if (w < T[i + k]) T[i + k] = w;
      };
    };

    if (T[tsize - 1] > limit) continue;
    printf("%d\n", p + 1);
    return 0;
  };

  printf("NIE\n");
  return 0;
}