Submission #893427

#	Time	Username	Problem	Language	Result	Execution time	Memory
893427		juliany2	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	232 ms	97800 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2507;
int n;
string s;
ll a, b, c;
ll dp[N][N];
int lcp[N][N], nxt[N][N];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> s >> a >> b >> c;
    s = " " + s;

    for (int i = n; i >= 1; i--)
        for (int j = n; j > i; j--)
            if (s[i] == s[j])
                lcp[i][j] = min(lcp[i + 1][j + 1] + 1, j - i);

    for (int i = 1; i <= n; i++) {
        vector<int> bst(n + 1, n + 1);
        int val = n + 1;
        for (int j = n; j >= i; j--) {
            nxt[i][j] = val;

            bst[lcp[i][j]] = j;
            if (lcp[i][j] >= j - i)
                val = j;
            val = min(val, bst[j - i]);
        }
    }

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

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

            int r = j;
            ll cost = b + c;
            while (nxt[r - (j - i)][r] <= n) {
                int skip = nxt[r - (j - i)][r] - r - 1;
                cost += a * skip + c;
                r += skip + 1 + (j - i);

                dp[i][r] = min(dp[i][r], dp[i][j] + cost);
            }
        }
    }

    cout << dp[1][n] << '\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