注意到「不失败」和「打大佬」是相互独立的，考虑先用一个简单 DP 求出不失败的情况下最多可以留出多少天来打大佬。
然后考虑 BFS 出所有可能的 \(F\) 值和达到它的天数的状态。
注意天数不同的方案要保留，因为也会有贡献。
然后把 \(F\) 值排序，用双指针优化一下判定过程。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using namespace std;
const int N = 100;
const int M = 20;
const int LEN = 1e6;
int n,m,mc;
int a[N + 5],w[N + 5],C[M + 5],lim;
int f[N + 5][N + 5],D;
tr1::unordered_map< int,tr1::unordered_set<int> > vis;
struct note
{
int l,d;
int f;
} q[LEN * 10 + 5];
int head,tail,tot;
pair<int,int> d[LEN + 5];
void bfs()
{
q[++tail] = (note){0,1,1},vis[1].insert(1),d[++tot] = make_pair(1,1);
for(register note p;head < tail;)
{
p = q[++head];
if(p.d < D)
{
q[++tail] = (note){p.l + 1,p.d + 1,p.f};
if(p.l > 1 && (long long)p.f * p.l <= lim && (!vis.count(p.f * p.l) || !vis[p.f * p.l].count(p.d + 1)))
q[++tail] = (note){p.l,p.d + 1,p.f * p.l},vis[p.f * p.l].insert(p.d + 1),d[++tot] = make_pair(p.f * p.l,p.d + 1);
}
}
}
inline bool cmp(pair<int,int> a,pair<int,int> b)
{
return a.first == b.first;
}
int main()
{
scanf("%d%d%d",&n,&m,&mc);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 1;i <= n;++i)
scanf("%d",w + i);
for(register int i = 1;i <= m;++i)
scanf("%d",C + i),lim = max(lim,C[i]);
memset(f,0x3f,sizeof f),f[0][mc] = 0;
for(register int i = 1;i <= n;++i)
for(register int j = a[i];j <= mc;++j)
f[i][min(j - a[i] + w[i],mc)] = min(f[i][min(j - a[i] + w[i],mc)],f[i - 1][j] + 1),
f[i][j - a[i]] = min(f[i][j - a[i]],f[i - 1][j]);
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= mc;++j)
D = max(D,i - f[i][j]);
bfs(),sort(d + 1,d + tot + 1),tot = unique(d + 1,d + tot + 1,cmp) - d - 1;
for(register int i = 1,flag;i <= m;++i)
{
if(C[i] <= D)
{
puts("1");
continue;
}
flag = 0;
int p1 = 1,p2 = 1,mx = -0x3f3f3f3f;
for(;p1 <= tot && d[p1].first <= C[i];++p1)
if(d[p1].first + D - d[p1].second >= C[i])
{
flag = 1;
break;
}
--p1;
if(flag)
{
puts("1");
continue;
}
for(;p1;--p1)
{
for(;p2 <= tot && d[p1].first + d[p2].first <= C[i];++p2)
mx = max(mx,d[p2].first - d[p2].second);
if(d[p1].first - d[p1].second + mx + D >= C[i])
{
flag = 1;
break;
}
}
putchar(flag ^ '0'),puts("");
}
}