Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 蜜汁wa，bool数组可过，int数组wa

Posted by 1901213331 at 2019-12-28 14:17:25 on Problem 1742
```//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;

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)) {
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;

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)) {
solve();

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

Followed by: