T0888 着色

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

const long long NEG = -(1LL << 60);

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

    int n, m, k, id;
    cin >> n >> m >> k >> id;
    string s;
    cin >> s;
    vector<long long> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];
    vector<string> pat(m);
    vector<long long> w(m);
    vector<int> col(m);
    for (int i = 0; i < m; i++) cin >> pat[i] >> w[i] >> col[i];

    // gains[x] : 位置 x 上每种颜色的「承诺长度 L -> 累计收益」
    // 同一位置同一颜色可以取多个模式；承诺长度取这些模式的最大长度，
    // 收益是所有长度不超过它的模式的收益之和。
    vector<vector<pair<int, vector<pair<int, long long>>>>> gains(n + 2);
    // raw[x] : (颜色, 长度) -> 该位置该颜色该长度的收益和
    vector<map<pair<int, int>, long long>> raw(n + 2);
    for (int i = 0; i < m; i++) {
        const string &t = pat[i];
        int len = (int)t.size();
        vector<int> pi(len, 0);
        for (int a = 1, j = 0; a < len; a++) {
            while (j > 0 && t[a] != t[j]) j = pi[j - 1];
            if (t[a] == t[j]) j++;
            pi[a] = j;
        }
        for (int x = 1, j = 0; x <= n; x++) {
            while (j > 0 && s[x - 1] != t[j]) j = pi[j - 1];
            if (s[x - 1] == t[j]) j++;
            if (j == len) {
                // 模式 i 在位置 x 处匹配结束，起点是 start = x-len+1：
                // 染颜色 col[i]，范围 [start, x]，收益 p[start]+w[i]
                int start = x - len + 1;
                raw[start][{col[i], len}] += p[start] + w[i];
                j = pi[j - 1];
            }
        }
    }
    // gains[x] : 位置 x 上每种颜色的「承诺长度 L -> 累计收益」
    // 同一位置同一颜色可以取多个模式；承诺长度取这些模式的最大长度，
    // 收益是所有长度不超过它的模式的收益之和。
    for (int x = 1; x <= n; x++) {
        map<int, vector<pair<int, long long>>> byColor;
        for (auto &e : raw[x]) byColor[e.first.first].push_back({e.first.second, e.second});
        for (auto &e : byColor) {
            sort(e.second.begin(), e.second.end());
            vector<pair<int, long long>> v;
            long long sum = 0;
            for (auto &f : e.second) { sum += f.second; v.push_back({f.first, sum}); }
            gains[x].push_back({e.first, v});
        }
    }

    // 状态：处理到位置 x，当前颜色 c（0 表示还没用过颜色），
    // y = 最近一次被染上 c 的位置，e = 当前颜色被「承诺」到的位置（<= y）。
    // dp[x*(m+1)+c] : key = y*(n+2)+e -> 最大收益
    const int W = m + 1;
    vector<map<long long, long long>> dp((size_t)(n + 2) * W);
    dp[(size_t)1 * W + 0][0] = 0;

    auto relax = [&](int x, int c, int y, int e, long long v) {
        if (x > n + 1) { x = n + 1; }
        auto &mp = dp[(size_t)x * W + c];
        long long key = (long long)y * (n + 2) + e;
        auto it = mp.find(key);
        if (it == mp.end() || it->second < v) mp[key] = v;
    };

    for (int x = 1; x <= n; x++) {
        for (int c = 0; c <= m; c++) {
            auto &mp = dp[(size_t)x * W + c];
            if (mp.empty()) continue;
            vector<pair<pair<int, int>, long long>> st;
            for (auto &e : mp) st.push_back({{(int)(e.first / (n + 2)), (int)(e.first % (n + 2))}, e.second});
            for (auto &s0 : st) {
                int y = s0.first.first, e = s0.first.second;
                long long v = s0.second;
                // 1) 位置 x 不染色（只有不在承诺区间里才可以）
                if (x > e) relax(x + 1, c, y, e, v);
                // 2) 用当前颜色 c 染色
                if (c > 0) {
                    relax(x + 1, c, max(y, x), e, v);       // 不取任何模式
                    for (auto &g : gains[x]) {
                        if (g.first != c) continue;
                        for (auto &f : g.second) {
                            relax(x + 1, c, max(y, x + f.first - 1), max(e, x + f.first - 1), v + f.second);
                        }
                    }
                }
                // 3) 换成另一种颜色
                for (int d = 1; d <= m; d++) {
                    if (d == c) continue;
                    if (c > 0 && x - y <= k) continue;      // 与最近的颜色 c 距离太近
                    if (x <= e) continue;                     // 承诺区间内不能换色
                    relax(x + 1, d, x, x, v);                 // 不取任何模式
                    for (auto &g : gains[x]) {
                        if (g.first != d) continue;
                        for (auto &f : g.second) {
                            relax(x + 1, d, x + f.first - 1, x + f.first - 1, v + f.second);
                        }
                    }
                }
            }
        }
    }

    long long ans = NEG;
    for (int c = 0; c <= m; c++) {
        for (auto &e : dp[(size_t)(n + 1) * W + c]) ans = max(ans, e.second);
    }
    cout << ans << '\n';
    return 0;
}