- 贼难的一道题
- 虽然算法都不难，但组合起来就是想不到
- 首先，最简单的一步，对所有大佬，嘲讽你减的自信值和你做水题回复自信值都是不变的，写个(dp)，设(dp[i][j])表示第(i)天自信值为(j)可以有多少天不刷题，这便是你最多可以用的天数
- 现在你的任务便是在这么多天怼死大佬
- 考虑到与大佬对怼最多两次，剩下的天数就还嘴，(bfs)暴力搜索出所有你可以造成的伤害和所花的时间，自己写(Hash)判重，去重后的方案不会很多
- 现在处理每个大佬看能不能恰好怼死他
- 把所有搜索出的方案按伤害从大到小排序
- 首先如果天数比生命还多就直接可以
- 枚举使用一次技能可不可以
- 枚举使用两次技能可不可以，用个单调栈降低一下复杂度。
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=100+5;
bool cmax(sign &a,sign b){return (a<b)?a=b,1:0;}
bool cmin(sign &a,sign b){return (a>b)?a=b,1:0;}
template<typename T>inline T read()
{
T f=1,ans=0;
char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
return ans*f;
}
template<typename T>inline void write(T x,char y)
{
if(x==0)
{
putchar('0');putchar(y);
return;
}
if(x<0)
{
putchar('-');
x=-x;
}
static char wr[20];
int top=0;
for(;x;x/=10)wr[++top]=x%10+'0';
while(top)putchar(wr[top--]);
putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
freopen("3724.in","r",stdin);
freopen("3724.out","w",stdout);
#endif
}
int n,m,mc;
int a[N],w[N];
int dp[N][N];
void input()
{
n=read<int>();m=read<int>();mc=read<int>();
For(i,1,n)a[i]=read<int>();
For(i,1,n)w[i]=read<int>();
}
int max_d;
const int inf=0x3f3f3f3f;
void init()
{
memset(dp,-inf,sizeof dp);
dp[0][mc]=0;
For(i,1,n)For(j,a[i],mc)
{
cmax(dp[i][j-a[i]],dp[i-1][j]+1);
cmax(dp[i][min(mc,j-a[i]+w[i])],dp[i-1][j]);
}
For(i,1,n)For(j,0,mc)cmax(max_d,dp[i][j]);
//write(max_d,'
');
}
const int maxn=2e6+5;
namespace Hash
{
const int p=163,mo=72739;
struct node{int f,l,nex;}e[maxn];
int head[mo+5],tt;
int temp;
void add(int x,int y)
{
temp=(1ll*x*p%mo+y+mo)%mo;
e[++tt]=(node){x,y,head[temp]};
head[temp]=tt;
}
int find(int x,int y)
{
temp=(1ll*x*p%mo+y+mo)%mo;
for(int i=head[temp];i;i=e[i].nex)
if(e[i].f==x&&e[i].l==y)return 1;
return 0;
}
}
struct mess
{
int d,F,L;
};
int top;
queue<mess>l;
int c[N],max_c;
struct con
{
int f,d;
bool operator < (const con &s)const {return f<s.f;}
}q[maxn];
void bfs()
{
mess u,v;
l.push((mess){1,1,0});
while(!l.empty())
{
u=l.front();l.pop();
if(u.d==max_d)continue;
l.push((mess){u.d+1,u.F,u.L+1});
if(u.L>1&&(1ll*u.F*u.L)<=max_c&&!Hash::find(u.F*u.L,u.L))
{
v=(mess){u.d+1,u.F*u.L,u.L};
l.push(v);
q[++top]=(con){v.F,v.d};
Hash::add(v.F,v.L);
}
}
}
void work()
{
int flag,k,Min;
For(i,1,m)c[i]=read<int>(),cmax(max_c,c[i]);
bfs();
sort(q+1,q+top+1);
For(i,1,m)
{
flag=0;
if(c[i]<=max_d){puts("1");continue;}
k=1;Min=inf;
Fordown(j,top,1)
{
if(c[i]>=q[j].f&&c[i]-q[j].f<=max_d-q[j].d){flag=1;break;}
while(k<=top&&q[k].f+q[j].f<=c[i])
{
cmin(Min,q[k].d-q[k].f);
k++;
}
if(max_d>=c[i]-q[j].f+q[j].d+Min){flag=1;break;}
}
write(flag,'
');
}
}
int main()
{
file();
input();
init();
work();
return 0;
}