#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define hash hashy
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 4e3 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;
const int md1 = 1e9 + 87, md2 = 1e9 + 123;
int n, a, b, c;
string s;
int dp[N][N];
int mx[N][N];
int sparse[N][N][15];
ii hash[N];
ii pw26[N];
ii get(int l, int r){
int temp1 = (hash[r].fi - hash[l - 1].fi * pw26[r - l + 1].fi + md1 * md1) % md1;
int temp2 = (hash[r].se - hash[l - 1].se * pw26[r - l + 1].se + md2 * md2) % md2;
return {temp1, temp2};
}
void process(){
cin >> n >> s >> a >> b >> c;
s = '*' + s;
pw26[0] = {1, 1};
for(int i = 1; i <= n; i++){
hash[i].fi = (hash[i - 1].fi * 31 + s[i] - 'a') % md1;
hash[i].se = (hash[i - 1].se * 37 + s[i] - 'a') % md2;
pw26[i].fi = (pw26[i - 1].fi * 31) % md1;
pw26[i].se = (pw26[i - 1].se * 37) % md2;
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(s[i] != s[j]){
mx[i][j] = mx[j][i] = 0;
continue;
}
int le = i, ri = n;
while(le < ri){
int mid = (le + ri + 1) >> 1;
if((mid + (j - i)) > n){
ri = mid - 1;
continue;
}
ii temp1 = get(i, mid), temp2 = get(j, mid + (j - i));
if(temp1 == temp2) le = mid;
else ri = mid - 1;
}
mx[i][j] = mx[j][i] = (le - i + 1);
//cout << i << " " << j << " " << mx[i][j] << "\n";
}
}
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++) sparse[i][j][0] = mx[i][j];
for(int j = 1; j <= 13; j++){
for(int k = 1; (k + (1LL << j) - 1) <= n; k++){
sparse[i][k][j] = max(sparse[i][k][j - 1], sparse[i][k + (1LL << (j - 1))][j - 1]);
// cout << i << " " << j << " " << k << "\n";
}
}
}
for(int i = 1; i <= n; i++) dp[i][i] = a;
for(int le = n; le >= 1; le--){
for(int ri = le + 1; ri <= n; ri++) dp[le][ri] = oo;
for(int ri = le; ri <= n; ri++){
dp[le][ri] = min(dp[le][ri], min(dp[le][ri - 1], dp[le + 1][ri]) + a);
vector<int> pos;
pos.pb(le);
int itr = ri + 1;
while(itr <= n){
for(int i = 13; i >= 0; i--){
if((itr + (1LL << i) - 1) > n) continue;
// cout << le << " " << ri << " " << itr << " " << i << " " << sparse[le][itr][i] << "\n";
if(sparse[le][itr][i] < (ri - le + 1)) itr += (1LL << i);
}
if(sparse[le][itr][0] < (ri - le + 1)) break;
pos.pb(itr);
itr += (ri - le + 1);
}
int cnt = 0;
for(auto it : pos){
// cout << "OK " << le << " " << ri << " " << it << "\n";
cnt++;
int rem = ((it + ri - le) - le + 1) - (ri - le + 1) * cnt;
// cout << it + (ri - le) << "\n";
if(cnt > 1) dp[le][it + (ri - le)] = min(dp[le][it + (ri - le)], dp[le][ri] + b + c * cnt + a * rem);
}
}
for(int ri = le; ri <= n; ri++){
// cout << le << " " << ri << " " << dp[le][ri] << "\n";
}
}
cout << dp[1][n] << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
//freopen("KEK.inp", "r", stdin);
//freopen("KEK.out", "w", stdout);
cin.tie(0);
process();
}
Compilation message
/tmp/cc8iyR83.o: in function `process()':
copypaste3.cpp:(.text+0xd9): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0xe0): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
copypaste3.cpp:(.text+0x11e): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0x12d): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0x13c): relocation truncated to fit: R_X86_64_PC32 against symbol `b' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0x14b): relocation truncated to fit: R_X86_64_PC32 against symbol `c' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0x15a): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0x1a6): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0x1ad): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0x1c4): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/cc8iyR83.o
copypaste3.cpp:(.text+0x1dc): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
