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
128
129
130
131
132
133
134
135
136
137
138
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <list>


using namespace std;


class Paczka {
	public:
	int flagi;
	long long masa;
};

static vector<int> rzeczy;
static vector<int> plecaki;
static list<Paczka> paczki;


bool compare_desc(int i1, int i2) {
	return i2 < i1;
}

bool compare_paczki(Paczka p1, Paczka p2) {
	return p2.masa < p1.masa;
}

void dodaj_paczki(int sum, int level, int flagi) {
	if (level < rzeczy.size() - 1) {
		dodaj_paczki(sum, level + 1, flagi);
	}
	int new_sum = sum + rzeczy[level];
	if (new_sum <= plecaki[0]) {
		Paczka paczka;
		paczka.masa = new_sum;
		paczka.flagi = flagi | (1 << level);
		paczki.push_back(paczka);
		if (level < rzeczy.size() - 1) {
			dodaj_paczki(paczka.masa, level + 1, paczka.flagi);
		}
	}
}

const char *byte_to_binary(int x)
{
    static char b[9];
    b[0] = '\0';

    int z;
    for (z = 128; z > 0; z >>= 1)
    {
        strcat(b, ((x & z) == z) ? "1" : "0");
    }

    return b;
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		int masa;
		scanf("%d", &masa);
		rzeczy.push_back(masa);
	}
	for (int i = 0; i < m; i++) {
		int plecak;
		scanf("%d", &plecak);
		plecaki.push_back(plecak);
	}
	sort(plecaki.begin(), plecaki.end(), compare_desc);
	//for (vector<int>::iterator it = plecaki.begin(); it != plecaki.end(); ++it) {
	//	printf("%d ", *it);
	//}
	//printf("\n");
	dodaj_paczki(0, 0, 0);
	//printf("sorting\n");
	paczki.sort(compare_paczki);
	//printf("done\n");
	list<Paczka> pojedyncze;
	for (int i = 0; i < rzeczy.size(); i++) {
		Paczka p;
		p.masa = rzeczy[i];
		p.flagi = 1 << i;
		pojedyncze.push_back(p);
	}
	pojedyncze.sort(compare_paczki);
	int uzyte_plecaki = 0;
	for (int i = 0; i < m && paczki.size() > 0; i++) {
		//show_paczki();
		int miejsce = plecaki[i];
		for (list<Paczka>::iterator it = paczki.begin(); it != paczki.end(); ++it) {
//			printf("paczka %d\n", it->masa);
			if (it->masa <= miejsce) {
//				printf(" do plecaka %d? ", miejsce);
				int j = i + 1;
				bool ok = true;
				for (list<Paczka>::iterator it2 = pojedyncze.begin(); it2 != pojedyncze.end() && ok; ++it2) {
					if (!(it2->flagi & it->flagi)) {
						if (j >= m || plecaki[j++] < it2->masa) {
							ok = false;
						}
					}
				}
				if (ok) {
					//printf("tak\n");
					uzyte_plecaki++;
					paczki.erase(it);
					for (list<Paczka>::iterator it2 = paczki.begin(); it2 != paczki.end();) {
						if (it->flagi & it2->flagi) {
							it2 = paczki.erase(it2);
						} else {
							++it2;
						}
					}
					for (list<Paczka>::iterator it2 = pojedyncze.begin(); it2 != pojedyncze.end();) {
						if (it2->flagi & it->flagi) {
							it2 = pojedyncze.erase(it2);
						} else {
							++it2;
						}
					}
					break;
//				} else {
//					printf("nie\n");
				}
			}
		}
	}
	if (paczki.size() == 0) {
		printf("%d\n", uzyte_plecaki);
	} else {
		printf("NIE\n");
	}
}