Submission #895998

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

copypaste3

#include<bits/stdc++.h>
#define MAXN 37
using namespace std;

const long long inf=1e15;
const long long mod=1000000000100011;

int n;
long long a,b,c;
char s[MAXN];

long long dp[MAXN][MAXN][MAXN][MAXN][2*MAXN];
bool li[MAXN][MAXN][MAXN][MAXN][2*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,int ll,int rr,int step){
    if(step>2*n)return inf;
    if(l==1 and r==n)return 0;

    if(li[l][r][ll][rr][step])return dp[l][r][ll][rr][step];
    li[l][r][ll][rr][step]=true;
    dp[l][r][ll][rr][step]=inf;

    if(l==0 and r==0){
        dp[l][r][ll][rr][step]=ff(ll,rr,ll,rr,step+1)+c;
        for(int i=1;i<=n;i++){
            dp[l][r][ll][rr][step]=min(dp[l][r][ll][rr][step],ff(i,i,ll,rr,step+1)+a);
        }
        return dp[l][r][ll][rr][step];
    }

    dp[l][r][ll][rr][step]=ff(0,0,l,r,step+1)+b;

    if(r<n){
        dp[l][r][ll][rr][step]=min(dp[l][r][ll][rr][step],ff(l,r+1,ll,rr,step+1)+a);
    }

    if(ll!=0 and r+(rr-ll+1)<=n and hesh(ll,rr)==hesh(r+1,r+(rr-ll+1))){
        dp[l][r][ll][rr][step]=min(dp[l][r][ll][rr][step],ff(l,r+(rr-ll+1),ll,rr,step+1)+c);
    }

    return dp[l][r][ll][rr][step];
}

int main(){

    cin>>n>>(s+1);
    cin>>a>>b>>c;

    cout<<ff(0,0,0,0,0)<<"\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