Submission #1351534

#TimeUsernameProblemLanguageResultExecution timeMemory
1351534bakhtiyarnCopy and Paste 3 (JOI22_copypaste3)C++20
0 / 100
1 ms836 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2500+5;
const int mod = 1e9+7;
int p = 53;

vector<int> divs[N];
int cont[N][N];
int cost[N][N];

string s; 

int powmod(int x, int y){
    if(!y) return 1;
    int res = powmod(x, y/2);
    if(y%2) return res * res % mod * x % mod;
    return res * res % mod;
}

int get_hash(int l, int r){
    int hash = 0;
    for(int i=l; i<=r; i++){
        hash += powmod(p, i-l) * (s[i]-'a'+1) % mod;
        hash %= mod;
    }
    return hash;
}

// for(int i=1; i<=n; i++) 
void solve(){
    int n; cin >> n;
    cin >> s; s = '%' + s;
    int A, B, C; cin >> A >> B >> C;

    for(int sz=1; sz<=n; sz++) {
        for(int i=1; i<=n; i++) cost[sz][i] = 1e18;
    }


    int ans = 1e18;
    for(int sz=1; sz<=n; sz++) {
        vector<int> hash(n+1);
        for(int i=1; i<=n; i++) {
            if(i+sz-1 > n) break;
            hash[i] = get_hash(i, i+sz-1);
        }
        
        for(int i=n; i>=1; i--){
            if(i+sz-1 > n) continue;
            cont[sz][i] = cont[sz][i+sz];
            if(hash[i] != hash[i+sz]) cont[sz][i] = i+sz-1;
        }


        for(int i=1; i<=n; i++) {
            if(i+sz-1 > n) break;
            cost[sz][i] = sz * A + B;
            for(int j: divs[sz]){
                if(j >= sz) break;
                // if(cont[j][i] < i+sz-1) continue;
                int till = min(cont[j][i] , i+sz-1);
                cost[sz][i] = min(cost[sz][i], cost[j][i]+(till-i+1) / j*C + (i+sz-1 - till) * A+B);
            }
        }

        map<int, vector<int>> mp;
        for(int i=1; i<=n; i++) {
            // if(sz == 3) cout << hash[i] << " ";
            mp[hash[i]].push_back(i);
        }

        vector<int> dp(n+1);
        for(int i=n; i>=1; i--){
            if(i+sz-1 > n) continue;
            dp[i] = 1;
            auto it = lower_bound(mp[hash[i]].begin(), mp[hash[i]].end(), i+sz);
            if(it == mp[hash[i]].end()) continue;
            dp[i] = dp[*it] + 1;
        }


        for(int i=1; i<=n; i++) {
            if(i+sz-1 > n) break;
            ans = min(ans, cost[sz][i] + dp[i] * C + (n-dp[i]*sz)*A);
        }

    }

    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i=1; i<N; i++){
        for(int j=i; j<N; j+=i) divs[j].push_back(i);
    }

    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...