Submission #1178519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178519		ace5	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	1706 ms	54192 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2505;

typedef long long ll;

int cl[maxn][maxn],zf[maxn],ans[maxn];
ll dp[maxn][maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,a,b,c;
    string s;
    cin >> n >> s >> a >> b >> c;
    for(int len = 1;len <= n+1;++len)
        for(int l = 0;l+len <= n+1;++l)
            cl[len][l] = n+1;
    for(int i = n-1;i >= 0;--i)
    {
        zf[i] = 0;
        int l = i,r = i;
        ans[1] = n+1;
        for(int j = i+1;j < n;++j)
        {
            ans[j-i+1] = n+1;
            zf[j] = 0;
            if(j <= r)
                zf[j] = min(r-j+1,zf[j-l+i]+j);
            while(j+zf[j] < n && s[j+zf[j]] == s[i+zf[j]])
                zf[j]++;
            ans[min(zf[j],(j-i))] = min(ans[min(zf[j],(j-i))],j); 
        }
        for(int len = n-i;len >= 1;--len)
            cl[len][i] = min(ans[len],cl[len+1][i]);
    }
    for(int l = n-1;l >= 0;--l)
    {
        vector<ll> mn(n,0);
        ll te = 0;
        for(int r = l;r < n;++r)
        {
            te = min(te,mn[r]);
            dp[l][r] = (l==r ? a : min({dp[l+1][r]+a,dp[l][r-1]+a,te + a * (r-l+1)}));
            int len = r-l+1,cpos = l;
            ll cmin = dp[l][r] + b - a * len + c;
            while(cpos != n+1)
            {
                mn[cpos+len-1] = min(mn[cpos+len-1],cmin);
                cmin += c - a*len;
                cpos = cl[len][cpos];      
            }
        }
    }
    cout << dp[0][n-1] << "\n";
}

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