记录编号	587566	评测结果	A
题目名称	[POJ 1742]硬币	最终得分	100
用户昵称	增强型图元文件	是否通过	通过
代码语言	C++	运行时间	0.302 s
提交时间	2024-04-09 11:18:33	内存使用	5.83 MiB

#include <bits/stdc++.h>
using namespace std;
const int MAXN=110;
int n,m;
int a[MAXN],c[MAXN];
bool f[100100];
int main(int argc, char** argv) {
	freopen("makecoins.in","r",stdin);
	freopen("makecoins.out","w",stdout);
	cin>>n>>m;
	while(n&&m){
		memset(a,0,sizeof(a));
		memset(c,0,sizeof(c));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=n;i++){
			cin>>c[i];
		}
		f[0]=1;
		for(int i=1;i<=n;i++){
			int tm=0,tx=1,tp=1;
			while(tx<c[i]){
				for(int j=m;j>=tp*a[i];j--){
					f[j]|=f[j-tp*a[i]];
				}
				tm++;
				tp*=2;
				tx+=tp;
			}
			tx-=tp;
			tm--;
			int r=c[i]-tx;
			for(int j=m;j>=r*a[i];j--){
				f[j]|=f[j-r*a[i]];
			}
		}
		int ans=0;
		for(int i=1;i<=m;i++){
			if(f[i])ans++;
		}
		cout<<ans<<endl;
		cin>>n>>m;
	}
	return 0;
}