记录编号	234832	评测结果	AAAAAAAAAA
题目名称	[Nescafé 17] 守卫者的挑战	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	1.313 s
提交时间	2016-03-09 17:34:42	内存使用	54.09 MiB

#define STATE 1000000
#define HashSize 10007
#define eps 1e-14

#include<cstdio>
#include<cstring>

using namespace std;

double p[210],ans;
int n,lim,s,a[210];bool now;

struct HashTable{
	double f[STATE];int c[STATE];
	int first[HashSize][205],siz,next[STATE],state[STATE];
	void init(){siz=0;memset(first,-1,sizeof(first));}
	void push_back(int sta,int k,double add){
		int _hash=(sta%HashSize+HashSize)%HashSize;
		for(int i=first[_hash][k];i!=-1;i=next[i])
		    if(state[i]==sta&&c[i]==k){f[i]+=add;return;}
		state[siz]=sta;next[siz]=first[_hash][k];
		f[siz]=add;c[siz]=k;first[_hash][k]=siz++;
	}
}dp[2];

int main()
{
    freopen("guarda.in","r",stdin);
	freopen("guarda.out","w",stdout);
	scanf("%d%d%d",&n,&lim,&s);
	for(int i=1;i<=n;i++)scanf("%lf",&p[i]),p[i]/=100.0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	dp[now=0].init();dp[now].push_back(s,0,1.0);
	for(int i=1;i<=n;i++){
		dp[now^=1].init();
		for(int k=0;k<dp[now^1].siz;k++)if(dp[now^1].f[k]>=eps){
            dp[now].push_back(dp[now^1].state[k],dp[now^1].c[k],dp[now^1].f[k]*(1-p[i]));
			dp[now].push_back(dp[now^1].state[k]+a[i],dp[now^1].c[k]+1,dp[now^1].f[k]*p[i]);
		}
	}
	for(int k=0;k<dp[now].siz;k++)
	    if(dp[now].state[k]>=0&&dp[now].c[k]>=lim)ans+=dp[now].f[k];
	printf("%0.6lf",ans);
}