Submission #1031242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031242		adaawf	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	392 ms	69764 KiB

copypaste3

#include <iostream>
#include <map>
using namespace std;
long long int c[3005], p[3005], f[3005][3005], g[3005][3005], mod = 1e9 + 7, b = 177013;
long long int cc[3005], pp[3005], bb = 228922;
long long int check(int i, int j) {
    return (c[j] - c[i - 1] * p[j - i + 1] % mod + mod) % mod;
}
long long int check2(int i, int j) {
    return (cc[j] - cc[i - 1] * pp[j - i + 1] % mod + mod) % mod;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n, x, y, z;
    string s;
    cin >> n >> s >> x >> y >> z;
    s = " " + s;
    p[0] = pp[0] = 1;
    for (int i = 1; i <= n; i++) {
        c[i] = (c[i - 1] * b + s[i] - 'a' + 1) % mod;
        cc[i] = (cc[i - 1] * bb + s[i] - 'a' + 1) % mod;
        p[i] = p[i - 1] * b % mod;
        pp[i] = pp[i - 1] * bb % mod;
    }
    for (int d = 1; d <= n; d++) {
        map<pair<long long int, long long int>, int> m;
        for (int i = n - d + 1; i >= 1; i--) {
            int j = i + d - 1;
            g[i][j] = 1e18;
            long long int h = check(i, j), k = check2(i, j);
            if (m.count({h, k})) f[i][j] = m[{h, k}];
            else f[i][j] = 0;
            if (j + d - 1 <= n) m[{check(j, j + d - 1), check2(j, j + d - 1)}] = j;
        }
    }
    for (int d = 1; d <= n; d++) {
        for (int i = 1; i <= n - d + 1; i++) {
            int j = i + d - 1;
            g[i][j] = min(g[i][j], x * d);
            g[i][j] = min(g[i][j], min(g[i + 1][j], g[i][j - 1]) + x);
            int h = i, l = 1;
            while (1) {
                h = f[h][h + d - 1];
                if (h == 0) break;
                int k = h + d - 1;
                l++;
                g[i][k] = min(g[i][k], g[i][j] + y + x * (k - i + 1 - l * d) + l * z);
            }
        }
    }
    cout << g[1][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