この問題には、次のような性質があります。

• いま、ロボットが \(k\) 段目にいるとする。「ここから \(l\) 段目に到達できるかどうか」は、「これまでどのような動き方をしてきたか」と関係ない。

（例えば、「\(0\) 以上の整数が書かれたカードの束を持っていて、カードを捨てるとそこに書かれた段数だけ階段を登ることができる。モチの置いてある段には登れない。」というような問題設定では、上の性質は成り立ちません。これまでに捨てたカードがこれからの行動に影響してしまうためです。）

上の性質を使うと、「いまいる段数」を状態として持つ DP を考えることができます。

次のような DP 配列を定義します。

• \(\operatorname{dp}[i]\coloneqq i\) 段目に登ることができるなら \(1\) 、できないなら \(0\)

すると、\(\operatorname{dp}[i]\) はモチの位置 \(B _ i\) とより低い段に登れるか \(\operatorname{dp}[0],\operatorname{dp}[1],\ldots,\operatorname{dp}[i-1]\) の情報を用いて計算できます。

具体的には、次のようにして求められます。

\[ \operatorname{dp}[i]=\left\lbrace\begin{matrix}0&\quad&({}^\exists j.\ B _ j=i)\\\displaystyle\bigvee_j \operatorname{dp}[i-A_j]&&(\textrm{otherwise.})\end{matrix}\right. \]

言葉にすると、「モチが設置されていない段は、\(A _ i\) 段前のどれかの段に登れるなら、登れる」です。

はじめは \(0\) 段目にいるので \(\operatorname{dp}[0]=1\) 、\(\operatorname{dp}[-n]=0\ (n\gt0)\) であることに注意して、上の式に従って \(\operatorname{dp}\) を \(i\) の昇順に求めていくことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>

int main() {
    using namespace std;

    unsigned long N;
    cin >> N;
    vector<unsigned long> A(N);
    for (auto &&a : A)
        cin >> a;

    unsigned long M;
    cin >> M;
    vector<unsigned long> B(M);
    for (auto &&b : B)
        cin >> b;

    unsigned long X;
    cin >> X;
    // dp[i] := i 段目に登れるか
    // available[i] := i 段目にモチがあるか
    vector<unsigned long> dp(X + 1), available(X + 1, 1);
    for (const auto b : B)
        available[b] = 0;

    // 0 段目には登れる
    dp[0] = 1;
    for (unsigned long i{1}; i <= X; ++i)
        if (!available[i])
            // モチがあると、登れない
            dp[i] = 0;
        else
            // モチがないとき、dp[i - a] の or が答え
            for (const auto a : A)
                if (i >= a)
                    dp[i] |= dp[i - a];

    cout << (dp[X] ? "Yes" : "No") << endl;

    return 0;
}