#include<bits/stdc++.h> using namespace std; void local() { #define taskname "" if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } } #define ll long long #define fi first #define se second #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;} template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;} const int N = 1e6 + 5; int n; string s; int a, b, c; namespace sub3 { bool check() { return n <= 30; } const int N = 30 + 5; const int mod = 1e9 + 321; const int base = 311; int Hash[N]; int po[N]; int get(int l, int r) { return (Hash[r] - 1ll * Hash[l - 1] * po[r - l + 1] + 1ll * mod * mod) % mod; } ll dp[N][N]; void solve() { reverse(s.begin(), s.end()); s = '#' + s; for(int i = 1; i <= n; i++) Hash[i] = (1ll * Hash[i - 1] * base + s[i]) % mod; po[0] = 1; for(int i = 1; i <= n; i++) po[i] = 1ll * po[i - 1] * base % mod; for(int l = n; l > 0; l--) { dp[l][l] = a; for(int r = l + 1; r <= n; r++) { dp[l][r] = 1ll * (r - l + 1) * a; for(int k = l; k < r; k++) { mini(dp[l][r], 1ll * (k - l + 1) * a + dp[k + 1][r]); int len = k - l + 1; int cntC = 1; for(int p = k + 1; p + len - 1 <= r; p++) { if(get(l, k) == get(p, p + len - 1)) { cntC++; p = p + len - 1; } } mini(dp[l][r], dp[l][k] + b + 1ll * cntC * c + 1ll * (r - l + 1 - 1ll * len * cntC) * a); } } } cout << dp[1][n]; } } namespace sub4 { bool check() { return n <= 2e2; } const int N = 2e2 + 5; const int mod = 1e9 + 321; const int base = 311; int Hash[N]; int po[N]; int get(int l, int r) { return (Hash[r] - 1ll * Hash[l - 1] * po[r - l + 1] + 1ll * mod * mod) % mod; } ll dp[N][N]; int cnt[N][N][N]; void solve() { reverse(s.begin(), s.end()); s = '#' + s; for(int i = 1; i <= n; i++) Hash[i] = (1ll * Hash[i - 1] * base + s[i]) % mod; po[0] = 1; for(int i = 1; i <= n; i++) po[i] = 1ll * po[i - 1] * base % mod; for(int l = 1; l <= n; l++) { for(int r = l; r <= n; r++) { int len = r - l + 1; for(int i = r + len; i <= n; i++) { cnt[l][r][i] = cnt[l][r][i - 1]; if(get(l, r) == get(i - len + 1, i)) { cnt[l][r][i] = cnt[l][r][i - len] + 1; } } } } for(int l = n; l > 0; l--) { dp[l][l] = a; for(int r = l + 1; r <= n; r++) { dp[l][r] = 1ll * (r - l + 1) * a; for(int k = l; k < r; k++) { mini(dp[l][r], 1ll * (k - l + 1) * a + dp[k + 1][r]); int len = k - l + 1; int cntC = 1 + cnt[l][k][r]; mini(dp[l][r], dp[l][k] + b + 1ll * cntC * c + 1ll * (r - l + 1 - 1ll * len * cntC) * a); } } } cout << dp[1][n]; } } int main() { fastio; local(); cin >> n >> s >> a >> b >> c; if(sub4::check()) sub4::solve(); }

copypaste3.cpp: In function 'void local()':
copypaste3.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~