Submission #896042

#	Time	Username	Problem	Language	Result	Execution time	Memory
896042		alexander707070	Copy and Paste 3 (JOI22_copypaste3)	C++14	15 / 100	3057 ms	1108 KiB

copypaste3

#include<bits/stdc++.h>
#define MAXN 207
using namespace std;
 
const long long inf=1e15;
const long long mod=1000000000100011;
 
int n,len;
long long a,b,c,curr;
char s[MAXN];
 
long long dp[MAXN][MAXN];
bool li[MAXN][MAXN];
 
long long hesh(int l,int r){
    long long res=0;
    for(int i=l;i<=r;i++){
        res*=26; res+=s[i]-'a';
        res%=mod;
    }
    return res;
}
 
long long ff(int l,int r){
    if(l>r)return 0;

    if(li[l][r])return dp[l][r];
    li[l][r]=true;

    dp[l][r]=min(ff(l,r-1)+a-b , ff(l+1,r)+a-b);

    for(int i=r;i>=l;i--){

        curr=hesh(i,r); len=r-i+1;
        long long cost=0;

        for(int f=l;f<=r;f++){
            if(f+len-1<=r and hesh(f,f+len-1)==curr){
                f+=len-1;
                cost+=c;
            }else{
                cost+=a;
            }
        }

        dp[l][r]=min(dp[l][r],ff(i,r)+cost);
    }

    dp[l][r]+=b;
    return dp[l][r];
}
 
int main(){
 
    cin>>n>>(s+1);
    cin>>a>>b>>c;
 
    cout<<ff(1,n)<<"\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