Submission #992027

#	Time	Username	Problem	Language	Result	Execution time	Memory
992027		snpmrnhlol	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	225 ms	98396 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 25e2;
const ll inf = 1e18;
char v[N];
int lcp[N][N];
int nxt[N][N];
ll dp[N][N];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>v[i];
    }
    int a,b,c;
    cin>>a>>b>>c;
    for(int i = n - 1;i >= 0;i--){
        for(int j = n - 1;j >=0;j--){
            if(v[i] == v[j]){
                lcp[i][j] = 1 + ((i == n - 1 || j == n - 1)?0:lcp[i + 1][j + 1]);
            }else lcp[i][j] = 0;
            nxt[i][j] = n;
            dp[i][j] = inf;
        }
    }
    for(int i = n - 1;i >= 0;i--){
        int k = i;
        int j = i + 1;
        while(k < n){
            j = max(j,k + 1);
            while(j < n && lcp[i][j] <= k - i){
                j++;
            }
            nxt[i][k] = j;
            k++;
        }
    }
    for(int i = n - 1;i >= 0;i--){
        for(int j = i;j < n;j++){
            if(i == j)dp[i][j] = min(dp[i][j],(ll)a);
            else dp[i][j] = min(dp[i][j],min(dp[i + 1][j],dp[i][j - 1]) + (ll)a);
            ///propogate
            int k = j;
            int cnt = 0;
            int length = j - i + 1;
            while(k < n){
                cnt++;
                //cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j] + b + c*cnt + a*(k - i + 1 - length*cnt)<<' '<<(k - i + 1 - length*cnt)<<'\n';
                dp[i][k] = min(dp[i][k],dp[i][j] + b + 1ll*c*cnt + 1ll*a*(k - i + 1 - length*cnt));
                k = nxt[k - length + 1][k] + length - 1;
            }
            //cout<<dp[i][j]<<' '<<nxt[i][j]<<' '<<i<<' '<<j<<'\n';
        }
    }
    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