Submission #1020040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020040		alexdd	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1667 ms	87848 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int n,a,b,c;
string s;
int dp[2505][2505];
int nxt[2505][2505];
void calc_nxt()
{
    for(int lun=1;lun<=n;lun++)
    {
        map<string,int> mp;
        for(int le=n-lun;le>=0;le--)
        {
            if(le+lun+lun-1<n) mp[s.substr(le+lun,lun)]=le+lun;
            string x = s.substr(le,lun);
            if(mp[x]==0) nxt[le][le+lun-1]=-1;
            else nxt[le][le+lun-1]=mp[x];
        }
    }
}
signed main()
{
    cin>>n>>s>>a>>b>>c;
    calc_nxt();
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            dp[i][j]=INF;
    for(int lun=1;lun<=n;lun++)
    {
        for(int le=0;le+lun-1<n;le++)
        {
            int ri=le+lun-1;
            dp[le][ri] = min(dp[le][ri], (ri-le+1)*a);
            if(ri+1<n) dp[le][ri+1] = min(dp[le][ri+1], dp[le][ri]+a);
            if(le-1>=0) dp[le-1][ri] = min(dp[le-1][ri], dp[le][ri]+a);

            int cur=nxt[le][ri],cnt=1;
            while(cur!=-1)
            {
                cnt++;
                dp[le][cur+lun-1] = min(dp[le][cur+lun-1], dp[le][ri] + b + cnt*c + (((cur+lun-1)-le+1)-cnt*lun)*a);
                cur = nxt[cur][cur+lun-1];
            }
        }
    }
    cout<<dp[0][n-1];
    return 0;
}

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