Submission #1132158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132158		Math4Life2020	Copy and Paste 3 (JOI22_copypaste3)	C++20	62 / 100	3095 ms	350312 KiB

copypaste3

//JOI Copy and Paste 3 (2022joid2p1?)
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 2505; const ll INF = 1e18;
const __int128 a1 = 123456789; const __int128 p1 = ((ll)1e9+7)*((ll)1e9+9);
__int128 s1[Nm+1];
__int128 expa1[Nm+1];
__int128 hsh1[Nm+1];
ll N; string s;
ll A,B,C;

unordered_map<ll,ll> dp[Nm+1]; //dp[len][hsh] -> val
map<pii,vector<ll>> locs; //{len,hsh} -> vector of positions

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> s >> A >> B >> C;
    expa1[0]=1;
    hsh1[0]=0;
    for (ll i=0;i<Nm;i++) {
        expa1[i+1]=(a1*expa1[i])%p1;
        s1[i]=s[i]-'a'+1;
        hsh1[i+1]=(a1*hsh1[i]+s[i]-'a'+1)%p1;
    }
    for (ll i=0;i<N;i++) {
        for (ll j=(i+1);j<=N;j++) {
            __int128 hv = hsh1[j]-expa1[j-i]*hsh1[i];
            hv = (hv + p1*(2-hv/p1))%p1;
            dp[j-i][hv]=INF;
            locs[{j-i,hv}].push_back(i);
        }
    }
    dp[0][0]=0;
    for (ll L=1;L<=N;L++) {
        for (ll i=0;i<=(N-L);i++) {
            __int128 hv0 = hsh1[i+L-1]-expa1[L-1]*hsh1[i];
            hv0 = (hv0 + p1*(2-hv0/p1))%p1;
            __int128 hv1 = (a1*hv0 + s1[i+L-1])%p1;
            __int128 hv2 = hsh1[i+L]-expa1[L-1]*hsh1[i+1];
            hv2 = (hv2 + p1*(2-hv2/p1))%p1;
            dp[L][hv1] = min(dp[L][hv1],A+dp[L-1][hv0]);
            dp[L][hv1] = min(dp[L][hv1],A+dp[L-1][hv2]); 
        }
        for (pii p0: dp[L]) {
            ll hsh = p0.first; ll dpv = p0.second;
            if (locs[{L,hsh}].size()==1) {continue;}
            vector<ll> vlc = locs[{L,hsh}];
            sort(vlc.begin(),vlc.end());
            for (ll x: vlc) {
                ll y = x;
                ll njp = 0;
                while(1) {
                    auto A0 = lower_bound(vlc.begin(),vlc.end(),y);
                    if (A0==vlc.end()) {
                        break;
                    } else {
                        njp++;
                        y = (*A0)+L;
                        //string chars in range [x,y)
                        __int128 hv0 = hsh1[y]-hsh1[x]*expa1[y-x];
                        hv0 = (hv0+p1*(2-hv0/p1))%p1;
                        dp[y-x][hv0]=min(dp[y-x][hv0],A*(y-x-njp*L)+B+dpv+C*njp);
                    }
                }
            }
        }
    }
    cout << dp[N][hsh1[N]] <<"\n";
}

//for a stored sub-block S0 (length x): 
//x starting positions
//if O-tilde(#(occurrences of S0)^2):
//sum over x=x0: O(N^2) worst case -> bad.
//wait no: should (???) amortize to O(N^2logN)???
//ok imma code it

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 0 / 38