Submission #951801

#	Time	Username	Problem	Language	Result	Execution time	Memory
951801		EJIC_B_KEDAX	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	828 ms	315812 KiB

copypaste3

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef LOCAL
    // #pragma GCC optimize("O3")
    // #pragma GCC optimize("Ofast")
    // #pragma GCC optimize("unroll-loops")
    // #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937_64 mt(time(0));

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    cout << fixed << setprecision(30);
    init();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

const int N = 2525;
const ll mod = (1ll << 61) - 1, p = 31;
ll dp[N][N], save[N][N], mn[N];
int to[N][N], nw[N][N];
ll hsh[N], pdeg[N], pinv[N];
vector<pair<int, int>> upd[N];

ll add(ll a, ll b) {
    return a + b >= mod ? a + b - mod : a + b;
}

ll sub(ll a, ll b) {
    return a >= b ? a - b : a - b + mod;
}

ll mul(ll a, ll b) {
    return (__int128_t)1 * a * b % mod;
}

ll bin_pow(ll a, ll x) {
    ll res = 1;
    while (x) {
        if (x & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        x >>= 1;
    }
    return res;
}

ll inv(ll a) {
    return bin_pow(a, mod - 2);
}

void init() {
    pdeg[0] = 1;
    pdeg[1] = p;
    pinv[0] = 1;
    pinv[1] = inv(p);
    for (int i = 2; i < N; i++) {
        pdeg[i] = mul(pdeg[i - 1], p);
        pinv[i] = mul(pinv[i - 1], pinv[1]);
    }
}

ll get_hash(int l, int r) {
    return mul(sub(hsh[r + 1], hsh[l]), pinv[l]);
}

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int a, b, c;
    cin >> a >> b >> c;
    hsh[0] = 0;
    for (int i = 0; i < n; i++) {
        hsh[i + 1] = add(hsh[i], mul(s[i] - 'a' + 1, pdeg[i]));
        upd[i].reserve(40 * N);
    }
    for (int l = 0; l < n; l++) {
        unordered_map<ll, int> mp;
        for (int i = 0; i < n - l; i++) {
            int j = i + l;
            ll nw = get_hash(i, j);
            if (mp.find(nw) == mp.end()) {
                to[i][j] = -1;
            } else {
                to[i][j] = mp[nw];
            }
            if (i >= l) {
                mp[get_hash(i - l, i)] = i - l;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        dp[i][i] = a;
        save[i][i] = b + c;
        mn[i] = min(mn[i], save[i][i]);
        nw[i][i] = to[i][i];
        if (to[i][i] != -1) {
            upd[i - to[i][i]].emplace_back(i, i);
        }
    }
    for (int l = 1; l < n; l++) {
        for (auto [i, j] : upd[l]) {
            int nxt = to[nw[i][j]][nw[i][j] + j - i];
            nw[i][j] = nxt;
            if (nxt >= 0) {
                upd[j - nxt].emplace_back(i, j);
            }
            save[j][i] += c - 1ll * (j - i + 1) * a;
            mn[j] = min(mn[j], save[j][i]);
        }
        for (int i = 0; i < n - l; i++) {
            int j = i + l;
            dp[i][j] = min(1ll * (j - i + 1) * a + mn[j], dp[i][j - 1] + a);
            save[j][i] += dp[i][j] + b + c - 1ll * (j - i + 1) * a;
            mn[j] = min(mn[j], save[j][i]);
            nw[i][j] = to[i][j];
            if (nw[i][j] != -1) {
                upd[j - nw[i][j]].emplace_back(i, j);
            }
        }
    }
    cout << dp[0][n - 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