Submission #1207870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207870		RaresFelix	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	592 ms	49676 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

#define int ll
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vll = vector<ll>;

const ll MOD1 = 1e9 + 7;
const ll MOD2 = 1e9 + 9;

ll lpow(ll v, ll e, ll MOD) {
    return !e ? 1 : (e & 1) ? v * lpow(v * v % MOD, e >> 1, MOD) %  MOD : 
        lpow(v * v % MOD, e >> 1, MOD);
}

ll inv(ll v, ll MOD) { return lpow(v, MOD - 2, MOD); }

struct hsher {
    int n;
    string s;
    vi V1, V2;
    hsher(string s0) : n(s0.size()), s(s0), V1(n, 0), V2(n, 0) {
        for(int i = 0; i < n; ++i) {
            V1[i] = V2[i] = s[i] - 'a' + 1;
            if(i) {
                V1[i] = (29 * V1[i - 1] % MOD1 + V1[i]) % MOD1;
                V2[i] = (29 * V2[i - 1] % MOD2 + V2[i]) % MOD2;
            }
        }
    }

    ii operator()(int st, int dr) {
        int re1 = V1[dr], re2 = V2[dr];
        if(st) {
            re1 = (re1 - V1[st - 1] * lpow(29, dr - st + 1, MOD1) % MOD1 + MOD1) % MOD1;
            re2 = (re2 - V2[st - 1] * lpow(29, dr - st + 1, MOD2) % MOD2 + MOD2) % MOD2;
        }
        return {re1, re2};
    }
};

const ll INF = 1e18;

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n; string s;
    int a, b, c;
    cin >> n >> s >> a >> b >> c;
    vector<vll> DP(n, vll(n, INF));
    for(int i = 0; i < n; ++i)
        DP[i][i] = a;
    hsher HSH(s);
    for(int len = 1; len <= n; ++len) {
        vector<pair<ii, int> > Ord;
        for(int i = 0; i + len - 1 < n; ++i) {
            Ord.push_back({HSH(i, i + len - 1), i});
        }
        sort(Ord.begin(), Ord.end());
        for(int st = 0; st < (int)Ord.size(); ++st) {
            int dr = st;
            while(dr + 1 < (int)Ord.size() && Ord[st].first == Ord[dr + 1].first) ++dr;
            vi P;
            for(int j = st; j <= dr; ++j) P.push_back(Ord[j].second);

            vi Urm(P.size(), -1);
            {
                int p = 0;
                for(int i = 0; i < (int)P.size(); ++i) {
                    while(p < (int)P.size() && P[p] - P[i] < len) ++p;
                    if(p >= (int)P.size()) break;
                    Urm[i] = p;
                }
            }

            for(int i = 0; i < (int)P.size(); ++i) {
                int p = P[i], st0 = P[i], id = i;
                int cost0 = b + DP[p][p + len - 1];
                int cost_cur = c;

                while(p < n) {
                    DP[st0][p + len - 1] = min(DP[st0][p + len - 1], cost0 + cost_cur);
                    if(Urm[id] == -1) break;
                    cost_cur += c + a * (P[Urm[id]] - p - len);
                    id = Urm[id];
                    p = P[id];
                }
            }
            st = dr;
        }

        for(int i = 0; i + len < n; ++i) {
            DP[i][i + len] = min({DP[i][i + len], DP[i + 1][i + len] + a,
                    DP[i][i + len - 1] + a});
        }
    }
    cout << DP[0][n - 1] << "\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