Submission #634583

#	Time	Username	Problem	Language	Result	Execution time	Memory
634583		alvingogo	Copy and Paste 3 (JOI22_copypaste3)	C++14	15 / 100	3067 ms	26964 KiB

copypaste3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

string s;
int n,a,b,c;
const int bs=149,mod=20021213;
vector<int> pre,fac;
vector<vector<int> > g;
map<int,int> dp;
int inv(int x){
    return x==1?1:(inv(mod%x)*(mod-mod/x)%mod);
}
void init(){
    pre.resize(n+5);
    fac.resize(n+5);
    fac[0]=1;
    pre[0]=0;
    for(int i=1;i<=n;i++){
        fac[i]=fac[i-1]*bs%mod;
        pre[i]=(pre[i-1]+fac[i]*(s[i-1]-'a'+8))%mod;
    }
}
int ha(int l,int r){
    l++;
    r++;
    return (pre[r]-pre[l-1]+mod)*inv(fac[l])%mod;
}
int get(int l,int r){
    if(dp.find(g[l][r])!=dp.end()){
        return dp[g[l][r]];
    }
    int ans=(r-l+1)*a;
    map<int,pair<int,pair<int,int> > > m;
    for(int i=l;i<=r;i++){
        for(int j=1;i+j-1<=r;j++){
            auto z=g[i][i+j-1];
            if(m.find(z)!=m.end()){
                if(m[z].sc.sc<i){
                    m[z].fs++;
                    m[z].sc={i,i+j-1};
                }
            }
            else{
                m[z]={1,{i,i+j-1}};
            }
        }   
    }
    for(auto h:m){
        if(h.sc.fs<=1){
            continue;
        }
        int p=get(h.sc.sc.fs,h.sc.sc.sc);
        ans=min(ans,p+a*(r-l+1-h.sc.fs*(h.sc.sc.sc-h.sc.sc.fs+1))+b+c*h.sc.fs);
    }
    return dp[g[l][r]]=ans;
}
signed main(){
    AquA;
    cin >> n >> s >> a >> b >> c;
    init();
    g.resize(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            g[i][j]=ha(i,j);
        }
    }
    cout << get(0,n-1) << "\n";
    return 0;
}

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