//ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define M 100000+10
#define N 105
#define INF 0x3f3f3f3f
#pragma warning(disable:4996)
using namespace std;

int n, m;
bool f[M];
int a[N], c[N];
int sum;

void read() {
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < n; i++)
		scanf("%d", &c[i]);
}
void completepack(int t) {
	for (int i = t; i <= m; i++) {
		f[i] |= f[i - t];
	}
}
void zeroonepack(int t) {
	for (int i = m; i >= t; i--) {
		f[i] |= f[i - t];
	}
}
void solve() {
	memset(f, false, M * sizeof(bool));
	f[0] = true;
	sum = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] * c[i] >= m)
			completepack(a[i]);
		else {
			int k = 1;
			int num = c[i];
			while (k < num) {
				zeroonepack(k * a[i]);
				num -= k;
				k *= 2;
			}
			zeroonepack(num * a[i]);
		}
	}
	for (int i = 1; i <= m; i++)
		if (f[i] == 1)
			sum++;
}



int main() {
	while (scanf("%d %d", &n, &m) && (n != 0 || m != 0)) {
		read();
		solve();

		printf("%d\n", sum);
	}
	return 0;
}

//wa代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define M 100000+10
#define N 105
#define INF 0x3f3f3f3f
#pragma warning(disable:4996)
using namespace std;

int n, m;
int f[M];
int a[N], c[N];
int sum;

void read() {
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < n; i++)
		scanf("%d", &c[i]);
}
void completepack(int t) {
	for (int i = t; i <= m; i++) {
		f[i] = max(f[i - t],f[i]);
	}
}
void zeroonepack(int t) {
	for (int i = m; i >= t; i--) {
		f[i] = max(f[i - t], f[i]);
	}
}
void solve() {
	memset(f, 0, M * sizeof(int));
	f[0] = 1;
	sum = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] * c[i] >= m)
			completepack(a[i]);
		else {
			int k = 1;
			int num = c[i];
			while (k < num) {
				zeroonepack(k * a[i]);
				num -= k;
				k *= 2;
			}
			zeroonepack(num * a[i]);
		}
	}
	for (int i = 1; i <= m; i++)
		if (f[i] == 1)
			sum++;
}



int main() {
	while (scanf("%d %d", &n, &m) && (n != 0 || m != 0)) {
		read();
		solve();

		printf("%d\n", sum);
	}
	return 0;
}

• Re:蜜汁wa，bool数组可过，int数组wa (2474) TangYijie 2020-12-03 18:57:28