Submission #938614

#	Time	Username	Problem	Language	Result	Execution time	Memory
938614		Pannda	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	347 ms	74272 KiB

copypaste3

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

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

    int n;
    string s;
    int a, b, c;
    cin >> n >> s >> a >> b >> c;

    const long long INF = 2e18;
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, INF));
    vector<vector<int>> link(n, vector<int>(n + 1, n));

    for (int begin = n - 1; begin >= 0; begin--) {
        vector<int> z(n, 0);
        for (int i = begin + 1, l = 0, r = 0; i < n; i++) {
            if (i < r) z[i] = min(r - i, z[begin + i - l]);
            while (s[begin + z[i]] == s[i + z[i]]) z[i]++;
            if (i + z[i] > r) {
                l = i;
                r = i + z[i];
            }
        }
        dp[begin][begin] = 0;
        for (int len = 1, j = begin; len <= n - begin; len++) {
            dp[begin][begin + len] = min(dp[begin][begin + len], dp[begin][begin + len - 1] + a);
            dp[begin][begin + len] = min(dp[begin][begin + len], dp[begin + 1][begin + len] + a);
            link[begin][len] = n;
            j = max(j, begin + len);
            while (j < n && z[j] < len) {
                j++;
            }
            link[begin][len] = j;
            int cur = link[begin][len];
            int cnt = 1;
            while (cur < n) {
                cnt++;
                dp[begin][cur + len] = min(dp[begin][cur + len], dp[begin][begin + len] + b + 1LL * cnt * c + 1LL * (cur + len - begin - len * cnt) * a);
                cur = link[cur][len];
            }
        }
    }
    cout << dp[0][n] << '\n';
}

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