Overview

The cards we ultimately keep must be chosen as a subsequence of the original string \(S\).
We use interval DP to determine whether all unchosen consecutive segments can be eliminated, and then use DP to check whether we can construct the target string \(T\).

Key Observations

First, an important point: the integer sequence \(Q\) written on the cards does not affect the judgment.

For cards we keep, we can simply write the corresponding \(Q_i\) as specified.
On the other hand, the integers written on cards to be eliminated can be chosen freely. Since \(M \geq 1\), we can, for example, write the integer \(1\) on all cards to be eliminated.

Therefore, whether elimination is possible essentially depends only on:

• Whether the two cards in a pair have the same color

The characters are irrelevant to the elimination condition, and the integers can be freely matched.

---

Next, let’s consider the condition under which an entire consecutive segment \([l,r]\) can be eliminated.

When eliminating the entire segment \([l,r]\), the leftmost card \(l\) must be paired with some card \(k\) and eliminated together.
For this, the following conditions are necessary:

1. \(P_l = P_k\)
2. The segment \([l+1,k-1]\) between \(l\) and \(k\) can be entirely eliminated first
3. The segment \([k+1,r]\) to the right of \(k\) can also be entirely eliminated

This allows us to use interval DP to determine “whether this entire segment can be eliminated.”

---

Let the positions of the cards we ultimately keep be

\(1 \leq x_1 < x_2 < \cdots < x_L \leq N\)

Naturally, we need

\(S_{x_j} = T_j\)

Furthermore, since all cards not kept must be eliminated, the following segments must all be eliminable:

• \([1, x_1-1]\)
• \([x_1+1, x_2-1]\)
• \(\cdots\)
• \([x_L+1, N]\)

For example, if the kept positions are \(x_1,x_2,x_3\), cards between them cannot be eliminated across a kept card, so each gap must be independently eliminable.

Brute-force enumeration of all possible kept positions would result in a combinatorial explosion, so we use DP for efficient evaluation.

Algorithm

1. Determine whether a segment can be eliminated

Let \(E[l][r]\) be “true if all cards in segment \([l,r]\) can be eliminated.”

We define empty segments as eliminable:

\(E[i][i-1] = true\)

If the segment length is odd, since cards can only be eliminated in pairs, it is always false.

For segments \([l,r]\) of even length, we try each possible pairing partner \(k\) for the leftmost card \(l\).

The conditions are as follows:

If \(P_l = P_k\)

and \(E[l+1][k-1] = true\)

and \(E[k+1][r] = true\)

then \(E[l][r] = true\).

It suffices to try only \(k = l+1, l+3, \ldots, r\). This is because both sub-segments need to have even length.

---

2. Transition from the previously kept position to the next kept position

Next, we perform DP to construct the target string \(T\).

Prepare canPrev[i] as a bitset, where

• canPrev[i][p] = 1

means that if the previously kept card’s position is \(p\) and the next kept card’s position is \(i\), then the segment \([p+1, i-1]\) between them can be entirely eliminated.

Here, \(p=0\) represents “nothing has been kept yet,” i.e., before the beginning.

Also, store in endOk[p] whether the segment \([p+1,N]\) after the last kept position \(p\) can be eliminated.

---

3. DP to construct target string \(T\) from left to right

Let prev be a bitset, where

• prev[p] = 1

means “we have successfully constructed the prefix of \(T\) up to this point, and the last kept card’s position is \(p\).”

The initial state, with nothing selected yet, is:

• prev[0] = 1

When processing target character \(T_j\), for each card position \(i\):

• If \(S_i = T_j\)
• If prev and canPrev[i] share a common bit

then position \(i\) can be kept next.

In other words, the check is:

(prev & canPrev[i]).any()

After processing all of \(T\), the segment after the last kept position must be eliminable, so:

If (prev & endOk).any(), output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(N^3 + L N \lceil N/w \rceil)\)
  where \(w\) is the bitset word size. Overall, this is dominated by the interval DP’s \(O(N^3)\).
• Space complexity: \(O(N^2)\)

Implementation Notes

• The interval DP is easier to handle with 1-indexed arrays.

• Setting empty segments \([i,i-1]\) to true allows natural handling of segments of length \(2\), etc.

• \(Q\) needs to be read as input but is not used in the judgment. This is because we write the specified \(Q_i\) on kept cards, and the integers on eliminated cards can be chosen freely.

• If using fixed-size bitset, indices range from \(0\) to \(N\), so the size must be at least \(N+1\).

  Source Code

#include <bits/stdc++.h>
using namespace std;

static constexpr int MAXB = 505;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, L;
    cin >> N >> M >> L;

    string S, P, T;
    cin >> S >> P >> T;

    for (int i = 0; i < L; i++) {
        int x;
        cin >> x;
    }

    vector<vector<unsigned char>> erasable(N + 2, vector<unsigned char>(N + 2, 0));

    for (int i = 1; i <= N + 1; i++) {
        erasable[i][i - 1] = 1;
    }

    for (int len = 2; len <= N; len += 2) {
        for (int l = 1; l + len - 1 <= N; l++) {
            int r = l + len - 1;
            for (int k = l + 1; k <= r; k += 2) {
                if (P[l - 1] == P[k - 1] &&
                    erasable[l + 1][k - 1] &&
                    erasable[k + 1][r]) {
                    erasable[l][r] = 1;
                    break;
                }
            }
        }
    }

    auto ok = [&](int l, int r) -> bool {
        return l > r || erasable[l][r];
    };

    vector<bitset<MAXB>> canPrev(N + 1);

    for (int i = 1; i <= N; i++) {
        for (int p = 0; p < i; p++) {
            if (ok(p + 1, i - 1)) {
                canPrev[i].set(p);
            }
        }
    }

    bitset<MAXB> endOk;
    for (int p = 0; p <= N; p++) {
        if (ok(p + 1, N)) {
            endOk.set(p);
        }
    }

    bitset<MAXB> prev, cur;
    prev.set(0);

    for (int j = 0; j < L; j++) {
        cur.reset();

        for (int i = 1; i <= N; i++) {
            if (S[i - 1] == T[j] && (prev & canPrev[i]).any()) {
                cur.set(i);
            }
        }

        prev = cur;

        if (prev.none()) {
            cout << "No\n";
            return 0;
        }
    }

    cout << ((prev & endOk).any() ? "Yes\n" : "No\n");

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.