被一道简单BFS坑了这么长时间我也是hhh了
//By SiriusRen
#include <bits/stdc++.h>
using namespace std;
struct Node{int d,x,l;Node(int D=,int X=,int L=):d(D),x(X),l(L){}};
int n,m,mc,xx,a[],w[],maxx,f[][],top;
set<int>s[];pair<int,int>p[];
void BFS(){
queue<Node>q;q.push(Node(,,));
while(!q.empty()){
Node t=q.front();q.pop();
if(t.d<maxx){
q.push(Node(t.d+,t.x,t.l+));
if(t.l>&&t.x<=/t.l&&s[t.l].find(t.x*t.l)==s[t.l].end())
p[++top]=make_pair(t.x*t.l,t.d+),
s[t.l].insert(t.x*t.l),
q.push(Node(t.d+,t.x*t.l,t.l));
}
}
}
int main(){
memset(f,0xcf,sizeof(f));
scanf("%d%d%d",&n,&m,&mc),f[][mc]=;
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++)scanf("%d",&w[i]);
for(int i=;i<n;i++)
for(int j=;j<=mc;j++){
if(j-a[i+]>=)
f[i+][j-a[i+]]=max(f[i+][j-a[i+]],f[i][j]+),
f[i+][min(mc,j-a[i+]+w[i+])]=max(f[i+][min(mc,j-a[i+]+w[i+])],f[i][j]);
maxx=max(maxx,f[i][j]);
}
BFS(),sort(p+,p++top);
for(int i=;i<=m;i++){
scanf("%d",&xx);
int mn=0x3f3f3f3f;
if(xx<=maxx){puts("");goto ed2;}
for(int j=top,k=;j;--j)
{
while(k<top&&p[k+].first+p[j].first<=xx) ++k,mn=min(mn,p[k].second-p[k].first);
if(mn+p[j].second-p[j].first+xx<=maxx){puts("");goto ed2;}
if(p[j].first<=xx&&p[j].second+xx-p[j].first<=maxx){puts("");goto ed2;}
}
puts("");
ed2:;
}
}