Accepted/624K/1344MS

poj1742.cpp

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxs=105,maxm=100005;
bool f[maxm];
int w[maxs],b[maxs];
int sum[maxm];
int main()
{
	int n,v;
	while ((~scanf("%d%d",&n,&v)) && n)
	{
		int ans=0;
		for (int i=0;i<n;i++)
			scanf("%d",&w[i]);
		for (int j=0;j<n;j++)
			scanf("%d",&b[j]);
		for (int i=1;i<=v;i++)
			f[i]=0;
		f[0]=1;
		for (int i=0;i<n;i++)
		{
			for (int j=0;j<=v;j++)
				sum[j]=0;
			for (int j=w[i];j<=v;j++)
			{
				if (!f[j] && f[j-w[i]] && sum[j-w[i]]<b[i])
				{
					f[j]=1;
					sum[j]=sum[j-w[i]]+1;
					ans++;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}