luogu 黑题 P3724大佬

#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;
}