Submission #950542

#	Time	Username	Problem	Language	Result	Execution time	Memory
950542		hotboy2703	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	299 ms	197836 KiB

copypaste3

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll t;
string s;
ll a,b,c;
ll n;
const ll MAXN = 2500;
ll dp[MAXN+10][MAXN+10];
ll type[MAXN+10][MAXN+10];
ll nxt[MAXN+10][MAXN+10];
ll z[MAXN+10][MAXN+10];
vector <ll> all[MAXN+10];
ll best[MAXN + 10];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>t;
//    while (t--){
        cin>>s;
        cin>>a>>b>>c;
        n = sz(s);
        s = "x" + s;
        for (ll i = 1;i <= n;i ++){
            for (ll j = i + 1,l = 0,r = 0;j <= n;j ++){
                ll ptr;
                if (r > j)ptr = min(r,j+z[i][i+j-l]-1);
                else ptr = j-1;
                while (ptr+1<=n&&s[ptr+1]==s[i+ptr+1-j])ptr++;
                z[i][j] = ptr-j+1;
                if (ptr > r){
                    r = ptr;
                    l = j;
                }
            }
        }
        for (ll j = 1;j <= n;j ++){
            for (ll i = 1;i < j;i ++){
                if (best[j] == 0)best[j] = i;
                else{
                    if (z[best[j]][j] < z[i][j])best[j] = i;
                }
            }
        }
        for (ll k = 1;k <= n;k ++){
            ll ptr = 1;
            for (ll l = 1,r = k; r <= n; l++,r++){
                if (l==1)type[k][l] = ptr++;
                else{
                    if (z[best[l]][l] >= k)type[k][l] = type[k][best[l]];
                    else type[k][l] = ptr++;
                }
            }
        }
        for (ll k = 1;k <= n;k ++){
            for (ll i = 1;i <= n;i ++)all[i].clear();
            for (ll l = 1,r = k; r <= n; l++,r++){
                all[type[k][l]].push_back(l);
            }
            for (ll i = 1;i <= n;i ++){
                for (ll j = 0,ptr = 0;j < sz(all[i]);j ++){
                    while (ptr < sz(all[i]) && all[i][j] + k > all[i][ptr])ptr++;
                    if (ptr < sz(all[i]))nxt[k][all[i][j]] = all[i][ptr];
                    else nxt[k][all[i][j]] = -1;
                }
            }
//            for (ll l = 1,r = k; r <= n; l++,r++){
//                cout<<nxt[k][l]<<' ';
//            }
//            cout<<'\n';
        }
        for (ll k = 1;k <= n;k ++){
            for (ll l = 1,r = k; r <= n; l++,r++){
                dp[l][r] = (r-l+1)*a;
            }
        }
        for (ll k = 1;k <= n;k ++){
            for (ll l = 1,r = k; r <= n; l++,r++){
                if (l > 1)dp[l-1][r] = min(dp[l-1][r],dp[l][r]+a);
                if (r < n)dp[l][r+1] = min(dp[l][r+1],dp[l][r]+a);
                ll cur = l;
                ll cnt = 1;
                while (1){
                    cur = nxt[k][cur];
                    cnt++;
                    if (cur==-1)break;
                    dp[l][cur + k - 1] = min(dp[l][cur + k - 1],dp[l][r] + b + c * cnt + (cur+k-1-l+1-cnt*k)*a);
                }
            }
        }
//        cout<<dp[3][3]<<'\n';
        cout<<dp[1][n]<<'\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