Submission #703157

#	Time	Username	Problem	Language	Result	Execution time	Memory
703157		piOOE	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	432 ms	73876 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 2501;

ll dp[N][N];
int nxt[N][N], z[N];

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

    memset(nxt, -1, sizeof(nxt));

    int n;
    cin >> n;

    string s;
    cin >> s;

    int A, B, C;
    cin >> A >> B >> C;

    auto z_function = [&](int i) {
        memset(z, 0, sizeof(z));

        int l = i, r = i;

        for (int j = i + 1; j < n; ++j) {
            int k = 0;

            if (r > j) {
                k = min(r - j, z[i + (j - l)]);
            }

            while (j + k < n && s[j + k] == s[i + k]) {
                k += 1;
            }

            z[j] = k;

            if (j + k > r) {
                r = j + k;
                l = j;
            }
        }
    };

    memset(dp, 0x3f, sizeof(dp));

    for (int i = n - 1; i >= 0; --i) {
        z_function(i);

        int pnt = 1;

        for (int j = i + 1; j < n; ++j) {
//            cout << z[j] << " ";

            while (pnt <= z[j] && i + pnt <= j) {
                nxt[i][pnt++] = j;
            }
        }

//        for (int len = 1; len <= n - i; ++len) {
//            cout << nxt[i][len] << " ";
//        }
//
//        cout << endl;


        if (i + 1 < n) {
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = dp[i + 1][j] + A;
            }
        }

        dp[i][i] = A;

        for (int j = i; j < n; ++j) {
            if (j > 0) {
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + A);
            }

            int len = j - i + 1;
            int x = nxt[i][len];
            int cnt = 1;

            while (x != -1) {
                cnt += 1;
                int r = x + len - 1;

                dp[i][r] = min(dp[i][r], 1LL * (r - i + 1 - cnt * len) * A + dp[i][j] + B + 1LL * C * cnt);

                x = nxt[x][len];
            }
        }

//        for (int j = i; j < n; ++j) {
//            cout << dp[i][j] << " ";
//        }
//
//        cout << endl;
    }

    cout << dp[0][n - 1] << '\n';

    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38