Submission #688293

#	Time	Username	Problem	Language	Result	Execution time	Memory
688293		Darren0724	Copy and Paste 3 (JOI22_copypaste3)	C++17	20 / 100	3057 ms	49424 KiB

copypaste3

#pragma GCC optimize("Ofast","O3","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
const int INF=1e18;
int k=37,mod=1e9+7;
struct Hash{
    vector<int> pw,h;
    Hash(string s){
        int n=s.size();
        s=' '+s;
        pw.resize(n+2);
        h.resize(n+2);
        pw[0]=1;
        for(int i=1;i<=n;i++){
            pw[i]=pw[i-1]*k%mod;
            h[i]=h[i-1]*k+s[i]-'a'+1;
            h[i]%=mod;
        }
    }
    int get(int a,int b){
        a++;b++;
        int len=b-a;
        return ((h[b-1]-h[a-1]*pw[len])%mod+mod)%mod;
    }
};
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    string s;cin>>s;
    Hash h(s);
    int a,b,c;cin>>a>>b>>c;
    bool flag=0;
    for(int i=0;i<n;i++){
        if(s[i]!='a'){
            flag=1;
        }
    }
    if(flag==0){
          vector<vector<int>> dp(n+1,vector<int>(n+1,INF));
          dp[0][0]=0;
          for(int i=0;i<=n;i++){
            for(int j=i;j<=n;j++){
              dp[i][j]=min(dp[i][j],dp[i][j-i]+c);
              dp[i][j]=min(dp[i][j],dp[i][j-1]+a);
              dp[j][0]=min(dp[j][0],dp[i][j]+b);
            }
          }
          int ans=INF;
          for(int i=0;i<=n;i++){
            ans=min(ans,dp[i][n]);
          }
          cout<<ans<<endl;
          return 0;
    }
    //cout<<h.get(2,5)<<' '<<h.get(5,8)<<endl;
    vector<vector<int>> dp(n+2,vector<int>(n+2));
    for(int len=1;len<=n;len++){
        for(int i=0;i+len<=n;i++){
            int r=i+len;
            //cout<<i<<' '<<r<<endl;
            dp[i][r]=len*a+b;
            for(int i1=i;i1<r;i1++){
                for(int j1=i1+1;j1<=r;j1++){
                    int len1=j1-i1;
                    int cnt=0;
                    for(int p=i;p+len1<=r;p++){
                        if(h.get(i1,j1)==h.get(p,p+len1)){
                            cnt++;
                            p=p+len1-1;
                        }
                    }
                    dp[i][r]=min(dp[i][r],dp[i1][j1]+cnt*c+(len-len1*cnt)*a+b);
                }
            }
        }
    }
    cout<<dp[0][n]-b<<endl;

    return 0;
}

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