Submission #950521

#	Time	Username	Problem	Language	Result	Execution time	Memory
950521		hotboy2703	Copy and Paste 3 (JOI22_copypaste3)	C++14	30 / 100	3054 ms	134104 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];
vector <ll> all[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 k = 1;k <= n;k ++){
            ll ptr = 1;
            for (ll l = 1,r = k; r <= n; l++,r++){
                for (ll l1 = 1,r1 = k; l1 < l; l1++,r1++){
                    bool ok = 1;
                    for (ll j = 0;j < k;j ++){
                        if (s[j+l1] != s[j+l])ok = 0;
                    }
                    if (ok){type[k][l] = type[k][l1];break;}
                }
                if (type[k][l] == 0)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: 0 / 32
• Subtask 6: 0 / 38