Submission #938580

#	Time	Username	Problem	Language	Result	Execution time	Memory
938580		Pannda	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1638 ms	74076 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++) {
            while (s[begin + z[i]] == s[i + z[i]]) z[i]++;
        }
        dp[begin][begin] = 0;
        for (int len = 1; 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;
            for (int j = begin + len; j < n; j++) {
                if (z[j] >= len) {
                    link[begin][len] = j;
                    break;
                }
            }
            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';
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:19:33: warning: unused variable 'l' [-Wunused-variable]
   19 |         for (int i = begin + 1, l = 0, r = 0; i < n; i++) {
      |                                 ^
copypaste3.cpp:19:40: warning: unused variable 'r' [-Wunused-variable]
   19 |         for (int i = begin + 1, l = 0, r = 0; i < n; i++) {
      |                                        ^

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