Submission #1286638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286638		duckindog	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	356 ms	50072 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

const int N = 2500 + 10;
int n;
string s;
int A, B, C;

using ull = unsigned long long;
const ull base = 19937;
ull h[N], pw[N];
inline ull getHash(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }

vector<int> pos[N];
int nxt[N];

long long f[N][N];

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

    cin >> n;
    cin >> s;
    cin >> A >> B >> C;

    s = '@' + s;

    { // init hash
        pw[0] = 1;
        for (int i = 1; i <= n; ++i) { 
            h[i] = h[i - 1] * base + s[i];
            pw[i] = pw[i - 1] * base;
        }
    }

    memset(f, 14, sizeof f);
    for (int i = 1; i <= n; ++i) f[i][i] = A;
    for (int len = 1; len <= n; ++len) { 
        vector<ull> allH;
        for (int i = 1; i <= n - len + 1; ++i) allH.push_back(getHash(i, i + len - 1));
        sort(allH.begin(), allH.end());
        allH.erase(unique(allH.begin(), allH.end()), allH.end());

        for (int i = 1; i <= n - len + 1; ++i) { 
            int it = upper_bound(allH.begin(), allH.end(), getHash(i, i + len - 1)) - allH.begin();
            pos[it].push_back(i);
        }

        fill(nxt + 1, nxt + n + 1, 0);
        for (int idx = 1; idx <= (int)allH.size(); ++idx) { 
            for (int i = 0, it = 0; i < (int)pos[idx].size(); ++i) { 
                for (; pos[idx][it] + len - 1 < pos[idx][i]; ++it) nxt[pos[idx][it]] = pos[idx][i];
            }
            pos[idx].clear();
        }

        for (int l = n - len + 1; l >= 1; --l) { 
            const int r = l + len - 1;

            { // cur
                auto& ret = f[l][r];
                ret = min({ret, f[l + 1][r] + A, f[l][r - 1] + A});
            }

            { // update
                long long updCost = f[l][r] + B + C;
                for (int j = nxt[l], last = l; j; last = j, j = nxt[j]) { 
                    updCost += 1ll * (j - last - len) * A + C;
                    auto& ret = f[l][j + len - 1];
                    ret = min(ret, updCost);
                }
            }
        }
    }
    
    cout << f[1][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