Submission #1121246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121246		vjudge1	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	331 ms	128244 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define all(x) x.begin(),x.end()
#define int long long

typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;

const ll maxn=2500+5;
const ll offset=2e5;
const ll inf=1e18;
const int base=350;
const ll mod=998244353;

int n,a,b,c;
string s;
int dp[maxn][maxn],lcp[maxn][maxn],nxt[maxn][maxn];

void sol()
{
    cin >> n>> s>>a>>b>>c;
    s='$'+s;
    for1(len,1,n)
    {
        for2(i,n-len+1,1)
        {
            int j=i+len-1;
            if (s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;
        }
    }
    for1(i,1,n)
    {
        int pos=i+1;
        for1(j,i,n)
        {
            while (pos<=n && (lcp[i][pos] < j-i+1 || pos<=j)) pos++;
            nxt[i][j]=pos;
//            cerr<< i<<' '<<j<<' '<<pos<<'\n';
        }
    }
//    return;
    for1(i,0,n+1) for1(j,0,n+1) dp[i][j]=inf;
    for1(len,1,n)
    {
        for1(i,1,n-len+1)
        {
            int j=i+len-1;
            dp[i][j]=min(dp[i][j],len*a);
            dp[i][j]=min(dp[i][j],dp[i][j-1]+a);
            dp[i][j]=min(dp[i][j],dp[i+1][j]+a);
//            if (i==2 && j==5) cerr<< i<<' '<<j<<' '<<dp[i][j]<<"\n";
            int cur=i,cnt=1;
            while(1)
            {
                ++cnt;cur=nxt[cur][cur+len-1];
                if (cur>n) break;
                dp[i][cur+len-1]=min(dp[i][cur+len-1],dp[i][j]+c*cnt+b+(cur+len-1-i+1-cnt*len)*a);
//                if (i==2 && cur+len-1==8) cerr<<i<<' '<<j<<" dof "<< cur+len-1-i+1-cnt*len<<' '<<dp[i][cur+len-1]<<'\n';
            }
        }
    }
    cout<< dp[1][n];


}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("1017G.inp","r",stdin);
//    freopen("1017G.out","w",stdout);

    int t=1;//cin >> t;
    while (t--) {
        sol();
    }
}

/*
11
mississippi
10
5
2
*/

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