#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define max 111 #define ft(i) (zt[i].first) #define sd(i) (zt[i].second) inline int read() { rg int x=0,t=1;rg char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t; } int f[max][max]; int n,m,mc,day,a[max],w[max],c[max]; struct node{int i,f,l;}; pair<int,int> zt[1111111]; int tot,mx; int mod=1000007; struct hash { struct line{int x,y,next;}e[1111111]; int h[1000007+1],cnt; void add(int x,int y) { int pos=(1ll*x*101+y)%mod; e[++cnt]=(line){x,y,h[pos]};h[pos]=cnt; } bool query(int x,int y) { int pos=(1ll*x*101+y)%mod; for(int i=h[pos];i;i=e[i].next) if(e[i].x==x&&e[i].y==y)return true; return false; } }map; void bfs() { queue<node> q;q.push((node){1,1,0}); while(!q.empty()) { node u=q.front();q.pop(); if(u.i==day)continue; q.push((node){u.i+1,u.f,u.l+1}); if(u.l>1&&1ll*u.f*u.l<=1ll*mx&&!map.query(u.f*u.l,u.i+1)) { q.push((node){u.i+1,u.f*u.l,u.l}); zt[++tot]=make_pair(u.f*u.l,u.i+1); map.add(u.f*u.l,u.i+1); } } } int main() { n=read();m=read();mc=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<=n;++i)w[i]=read(); for(int i=1;i<=m;++i)mx=max(mx,c[i]=read()); for(int i=1;i<=n;++i) for(int j=a[i];j<=mc;++j) { f[i][j-a[i]]=max(f[i-1][j]+1,f[i][j-a[i]]); f[i][min(j-a[i]+w[i],mc)]=max(f[i-1][j],f[i][min(j-a[i]+w[i],mc)]); } for(int i=1;i<=n;++i) for(int j=1;j<=mc;++j)day=max(day,f[i][j]); bfs();sort(&zt[1],&zt[tot+1]); for(int i=1;i<=m;++i) { if(c[i]<=day){puts("1");continue;} bool fl=false;int mm=1e9; for(int j=tot,k=1;j;--j) { while(k<tot&&ft(k)+ft(j)<=c[i]) mm=min(mm,sd(k)-ft(k)),++k; if(mm+c[i]-ft(j)<=day-sd(j)){fl=true;break;} if(ft(j)<=c[i]&&c[i]-ft(j)<=day-sd(j)){fl=true;break;} } fl?puts("1"):puts("0"); } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603158.html