| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 890245 | amirhoseinfar1385 | Copy and Paste 3 (JOI22_copypaste3) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const short maxn=2500+10;
short lcp[maxn][maxn],nxt[maxn][maxn],n;
long long dp[maxn][maxn],a,b,c,inf=1e15;
string s;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>s;
cin>>a>>b>>c;
for(long long i=n-1;i>=0;i--){
for(long long j=i+1;j<n;j++){
if(s[i]==s[j]){
lcp[i][j]=lcp[i+1][j+1]+1;
}
}
}
for(long long i=0;i<maxn;i++){
for(long long j=0;j<maxn;j++){
nxt[i][j]=n+3;
}
}
for(long long i=0;i<n;i++){
for(long long j=n-1;j>i;j--){
nxt[i][min(lcp[i][j],j-i)]=j;
}
for(long long j=n;j>=0;j--){
nxt[i][j]=min(nxt[i][j],nxt[i][j+1]);
}
}
for(long long i=0;i<maxn;i++){
for(long long j=0;j<maxn;j++){
dp[i][j]=inf;
}
}
for(long long i=n-1;i>=0;i--){
dp[i][i]=a;
for(long long j=i+1;j<n;j++){
dp[i][j]=min(dp[i][j],min(dp[i+1][j],dp[i][j-1])+a);
}
for(long long j=1;j<n;j++){
dp[i][j+i-1]=min(dp[i][j+i-1],min(dp[i+1][j+i-1],dp[i][j+i-2])+a);
short ted=2;
long long z=dp[i][j+i-1];
for(long long h=nxt[i][j];h!=n+3;h=nxt[h][j]){
// cout<<i<<" "<<h<<" "<<j<<" "<<ted<<" "<<z<<" "<<endl;
dp[i][h+j-1]=min(dp[i][h+j-1],z+c*ted+b+a*(h+j-i-(ted*j)));
ted++;
}
}
for(long long j=i+1;j<n;j++){
dp[i][j]=min(dp[i][j],min(dp[i+1][j],dp[i][j-1])+a);
}
}
cout<<dp[0][n-1]<<"\n";
}