传送门

注意到题面里n很小，有\(n\leq100\)

考虑联系n的实际意义

n是你在大佬手中能活的天数

题面颇富深意

好了不闹了

n很小，对于\(40\%\)的数据，爆搜即可

考场上靠这个骗了40pts

对于满分做法

我是考完看了题解才开始写的

然而题解貌似写麻烦了

首先对大佬的伤害与特定日期无关，只与分配给蓄力/伤害的天数有关

所以先dp一下在保证不死的前提下最多能留出多少天输出

我们需要知道能否打出一个特定伤害

所以尝试爆搜一下，得到花费\(d\)时间可以打出的伤害\(f\)

回看题面，题面可转化为「对于每个\(c_i\)，问是否能构造出一种花费\(d\)天的怼大佬方案，使伤害\(f\leqslant c_i\)且\(f+md-d\geqslant c_i\)」，这里md为最多输出天数

已知所有的\(f\)和\(d\)，如何验证方案？

只怼一次或不怼\(O(n)\)扫一遍就好

怼两次，则需满足

（1）\(f_1+f_2 \leqslant c_i\)

（2）\(f_1+f_2+md-d_1-d_2 \geqslant c_i\)

（3）\(d_1+d_2 \leqslant md\)

将（2）移项，得\(f_1+f_2 \geqslant c_i+(d_1+d_2-md)\)

则满足（1）（2）必定同时满足（3）

仍然是区间取值问题，尝试将序列排序后固定一个端点

\(f_1, d_1, md\)固定，则check \(f_1+d_1+md+(f_2-d_2)_{max}\)是否\(\geqslant c_i\)即可

注意到这里\(f_1+f_2\)具有单调性，即（已由小到大排序过）对于\(f_i\)不可行的\(f_2\)，对于\(f_{i+1}\)同样不可行

所以采用双指针，每个左端点继承上个左端点的右端点进行扫描

时间复杂度就优化到了\(O(n)\)

对于那部分爆搜：

直接爆搜时间复杂度显然不对，考虑进行剪枝

这里出现了我以前没应用过的剪枝方法：利用\(hash\)进行判重

显然爆搜时对于相同的参数，所得结果应该是一样的，否则请先调试

那么把整个参数表hash掉，可完成记忆化

不过在这道题里更显著的应用是，

对于一个相同的f，我们只关心最小用时d，所以可以再开个hash表存

根据题解，我们可以采用bfs而不是dfs，因为bfs满足最先搜到某个f时天数一定是最小的，可以利用此性质优化hash表

p.s. 这个双指针的思路着实清奇

Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 110
#define MAXN 500010
#define ll long long
#define ld long double
#define usd unsigned
#define ull unsigned long long
//#define int long long 

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
char buf[1<<21], *p1=buf, *p2=buf;
inline int read() {
    int ans=0, f=1; char c=getchar();
    while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
    while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
    return ans*f;
}

int n, m, mc;
int a[N], w[N], c[25], md, size, mblood, cnt;
int dp[N][N];

struct plan{int d, f; inline void build(int d_, int f_) {d=d_; f=f_;} plan(int d_, int f_):d(d_),f(f_){} plan(){}}met[MAXN];
inline bool operator == (plan a, plan b) {return a.f==b.f&&a.d==b.d;}
inline bool operator < (plan a, plan b) {return a.f<b.f;}
struct ele{int d, f, l; ele(){} ele(int d_, int f_, int l_):d(d_),f(f_),l(l_){} inline void build(int d_, int f_, int l_){d=d_; f=f_; l=l_;}};
inline bool operator == (ele a, ele b) {return a.f==b.f&&a.d==b.d&&a.l==b.l;}

struct hush_map1{
    static const int SIZE=101000;
    int size, head[SIZE];
    hush_map1():size(0){memset(head, 0, sizeof(head));}
    struct node{int dat, next;}e[SIZE*10];
    inline bool operator [] (int q) {
        ll t = q%SIZE;
        for (int i=head[t]; i; i=e[i].next)
            if (e[i].dat==q) return 1;
        node* k=&e[++size]; k->dat=q; k->next=head[t]; head[t]=size;
        return 0;
    }
}mp1;

struct hush_map2{
    static const int SIZE=1010000;
    int size, head[SIZE];
    hush_map2():size(0){memset(head, 0, sizeof(head));}
    struct node{ele p; int next;}e[SIZE*10];
    inline bool operator [] (ele q) {
        ll t = (1ll*(q.d<<7)*q.f+q.l)%SIZE;
        for (int i=head[t]; i; i=e[i].next)
            if (e[i].p==q) return 1;
        if (size<SIZE) {node* k=&e[++size]; k->p=q; k->next=head[t]; head[t]=size;}
        return 0;
    }
}mp2;

struct hush_c{
    static const int SIZE=1000;
    int size, head[SIZE];
    hush_c():size(0){memset(head, 0, sizeof(head));}
    struct node{int p; bool vis; int next;}e[SIZE<<1];
    inline void operator [] (int q) {
        int t=q%SIZE;
        for (int i=head[t]; i; i=e[i].next)
            if (e[i].p==q) {
                if (!e[i].vis) e[i].vis=1,++cnt;
                break;
            }
    }
    void add(int q) {
        int t=q%SIZE;
        node* k=&e[++size]; k->p=q; k->vis=0; k->next=head[t]; head[t]=size;
    }
    bool query(int q) {
        int t=q%SIZE;
        for (int i=head[t]; i; i=e[i].next)
            if (e[i].p==q)
                return e[i].vis;
        puts("error");
    }
}test;

void checkout() {for (int i=1; i<=m; ++i) printf("%d\n", test.query(c[i]));}

signed main()
{
    #ifdef DEBUG
    freopen("1.in", "r", stdin);
    #endif

    //cout<<double(sizeof(met)+sizeof(mp1.head)+sizeof(mp1.e))/1024/1024<<endl;

    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) c[i]=read(), mblood=max(mblood, c[i]), test.add(c[i]);

    for (int i=n; i; --i)
        for (int j=a[i]; j<=mc; ++j)
            dp[i][j] = max(max(dp[i+1][j-a[i]]+1, dp[i+1][j-a[i]+w[i]]), dp[i][j-1]); //, printf("dp[%d][%d]=%d\n", i, j, dp[i][j]);
    md = dp[1][mc];
    //cout<<dp[1][mc]<<endl;
    for (int i=1; i<=m; ++i) if (c[i]<=md) test[c[i]];

    queue<ele> q;
    plan p; ele t, t2;
    q.push(ele(3, 1, 2));
    //met[++size].build(0, 0);
    while (!q.empty()) {
        t=q.front(); q.pop();
        //printf("%d %d\n", t.d, size);
        if (t.f>mblood) continue;

        if (t.f>1 && !mp1[t.f]) met[++size].build(t.d, t.f);
        //p.build(t.d, t.out+1);
        //if (!mp1[p]) met[++size]=p;

        if (t.d<md) {
            //printf("%d\n", mp2.size);
            #if 1
            t2.build(t.d+1, t.f, t.l+1);
            if (1ll*t.f*(t.l+1)<=mblood && !mp2[t2]) q.push(t2);
            t2.build(t.d+1, t.f*t.l, t.l);
            if (1ll*t.f*t.l<=mblood && !mp2[t2]) q.push(t2);
            #else
            if (1ll*t.f*(t.l+1)<=mblood) q.push(ele(t.d+1, t.f, t.l+1));
            if (t.f*t.l<=mblood) q.push(ele(t.d+1, t.f*t.l, t.l));
            #endif
        }
    }
    for (int i=1; i<=m; ++i) for (int j=1; j<=size; ++j) if (met[j].f<=c[i] && met[j].f+md-met[j].d>=c[i]) test[c[i]];
    //for (int i=1; i<=size; ++i) cout<<met[i].d<<' '<<met[i].f<<endl;
    //cout<<size<<endl<<endl;
    #if 0
    for (int i=1,t; i<=size; ++i)
        for (int j=md-met[i].d; j>=0; --j) {
            t = met[i].f+j;
            if (t) test[t], cout<<t<<endl;
        }
    if (cnt>=m) {checkout(); return 0;}
    #endif

    sort(met+1, met+size+1);
    for (int i=1,ci,val; i<=m; ++i) {
        ci = c[i];
        if (test.query(ci)) continue;
        plan *l=met+1, *r=met+size;
        while (l<=r) {
            val = md+l->f-l->d;
            //cout<<l-met<<' '<<r-met<<endl;
            while (l->f+r->f > ci) --r;
            //cout<<(val+r->f-r->d)<<endl;
            if (val+r->f-r->d >= ci) {test[ci]; /*cout<<"pos1"<<endl;*/ goto jump1;}
            ++l;
        }
        jump1: ;
    }
    checkout();

    return 0;
}