Submission #1178511

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

copypaste3

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2505;

typedef long long ll;

int cl[maxn][maxn];
ll dp[maxn][maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    ll a,b,c;
    cin >> a >> b >> c;
    for(int len = 1;len <= n;++len)
    {
        for(int l = 0;l+len <= n;++l)
        {
            cl[len][l] = -1;
        }
    }
    int zf[n];
    int ans[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;
            if(j > r)
            {
                l = j;
                int k = j;
                while(k < s.size() && s[i+k-j] == s[k])
                {
                    k++;
                }
                zf[j] = k-j;
                r = k-1;
            }
            else
            {
                int base = zf[i+j-l]+j-1;
                if(base < r)
                {
                    zf[j] = base-j+1;
                }
                else
                {
                    l = j;
                    int k = r+1;
                    while(k < s.size() && s[i+k-j] == s[k])
                    {
                        k++;
                    }
                    zf[j] = k-j;
                    r =k-1;
                }
            }
            // if(i == 2 && j == 8)
            //     cout << l << ' ' << r << ' ' << zf[j] << "!\n";
            ans[min(zf[j],(j-i))] = min(ans[min(zf[j],(j-i))],j); 
        }
       // cout << ans[1] << "!\n";
        int cans = n+1;
        for(int len = n-i;len >= 1;--len)
        {
            cans = min(cans,ans[len]);
            //if(len == 4 && i == 2)
            cl[len][i] = (cans == n+1 ? -1 : cans);
        }
        //cout << endl;
    }
    // for(int l = 0;l < n;++l)
    // {
    //     for(int r=  l;r < n;++r)
    //     {
    //         cout << cl[r-l+1][l] << ' ';
    //     }
    //     cout << endl;
    // }
   // cout << "!" << endl;
    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]);
            if(l == r)
            {
                dp[l][r] = a;
            }
            else
            {
                dp[l][r] = min({dp[l+1][r]+a,dp[l][r-1]+a,te + a * (r-l+1)});
            }
            int len = r-l+1;
            int cpos = l;
            ll cmin = dp[l][r] + b - a * (r-l+1) + c;
            // if(l == 0 && r == 3)
            // {
            //     cout << cmin << ' ';
            // }
            while(cpos != -1)
            {
                // if(l == 0 && r == 3)
                // {
                //     cout << cmin << ' ' << len << ' ' << cpos << ' ' << cl[len][cpos];
                // }
                mn[cpos+len-1] = min(mn[cpos+len-1],cmin);
                cmin += c - a*(r-l+1);
                cpos = cl[len][cpos];      
            }
           // cout << dp[l][r] << ' ';
        }
       // cout << "\n";
    }
    cout << dp[0][n-1] << "\n";
    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