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
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

char T1 [100000001];
char T2 [100000001];
int n,      m;
int a [24], c [100];

void wywal_z_a (int x){
//	printf ("Wywalam x=%d : ", x); for (int i= 0; i<n; i++) printf ("%d ", a[i]); printf ("\n");
	if (x == 0)
		return;
	int i;
	for (i = 0; a[i] < x; i++); // if (i == n); {printf ("Nie powinno cie tu byc!\n"); return;};
	n--;
	for (; i < n; i++)
		a[i] = a[i + 1];
}


// a posortowane rosnąco
bool bp_problem (int bp, int &w) { /// w jest wrzucony do bp. p to rozmiar plecaka
	w = 0;

	char *A = T1, *B = T2, tmp;
	for (int i = 0; i <= bp; i++)
		A[i] = B[i] = 0;

	for (int i = 0; i < n; i++){ // for every item
		if (a[i] > bp)
			break;
//printf ("Bp=%d  Item=%d\n", bp, a[i]);

		for (int j = 0; j < a[i]; j++)
			B[j] = A[j];

		for (int j = a[i]; j <= bp; j++){
			tmp = A[j - a[i]] + 1;
			if (tmp < A[j]){
				B[j] = A[j];
			} else {
				B[j] = tmp;
				if (j == bp){
//printf ("A:"); for (int e=0;e<=bp;e++) printf ("%d ", A[e]); printf ("\n");
//printf ("B:"); for (int e=0;e<=bp;e++) printf ("%d ", B[e]); printf ("\n");
					if (A[bp] <= B[bp])	
						w = a[i];
//printf ("w = %d\n", w);
				}
			}
		}

		if (B[bp] == 0)
			return false;

		swap (A, B);
	}
	if (A[bp] > 0)
		return true;

	return false;
}


int not_bp_problem ()
{
	sort (a, a + n);
	sort (c, c + m, greater<int> ());
	// c[0] == max weight
	
	
	int i, j, k, last;
	for (k = 0; n > 0 && k < m; k++){ // for every bp
//printf ("== BP o pojemnosci %d\n", c[k]);

		while (bp_problem (c[k], last))
		{
//printf ("  Wrzucam do niego %d\n", last);
			wywal_z_a (last);
			c[k] -= last;
		}

//printf ("# zostalo %d itemkow\n", n);
//printf ("Kolejny plecak.\n");
	}

	return (n > 0? 0 : k);
}

int main ()
{
	int i;
	scanf ("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf ("%d", &a[i]);
	for (i = 0; i < m; i++)
		scanf ("%d", &c[i]);

	if ((i = not_bp_problem ()) != 0)
		printf ("%d\n", i);
	else
		printf ("NIE\n");

	return 0;
}