使用二进制优化的背包,不知道是哪里错了啊 QAQ 有好心人看看嘛
#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[500010], a[210], k[210];
inline bool is_digit(char c) {
return c <= '9' && c >= '0';
}
inline int read() {
int tmp = 0;
char c = getchar();
while(!is_digit(c)) c = getchar();
while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
return tmp;
}
inline void write(int x) {
if(x > 9) write(x / 10);
putchar((x % 10) ^ 48);
}
int main() {
n = read(), m = read();
for(register int i = 1; i <= n; i++) {
k[i] = read(), a[i] = read();
}
f[0] = 1;
for(register int i = 1; i <= n; i++) {
if(a[i] >= 500000 / k[i]) {
for(register int j = k[i]; j <= m; j++) f[j] |= f[j - k[i]];
} else {
int L;
for(L = 1; (1 << L) <= a[i]; L++) {
for(int j = 500000; j >= (1 << L - 1) * k[i]; j--)
f[j] |= f[j - (1 << L - 1) * k[i]];
}
L--;
for(int j = 500000; j >= (a[i] - (1 << L) + 1) * k[i]; j--)
f[j] |= f[j - (a[i] - (1 << L) + 1) * k[i]];
}
}
while(m--) {
int qwq = read();
if(f[qwq]) puts("Yes");
else puts("No");
}
return 0;
}