#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() { 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] = a + dp[l + 1][r]; for(int k = l; k < r; k++) { int len = k - l + 1; int cntC = 1 + cnt[l][k][r]; //cout << l << ' ' << r << ' ' << dp[l][k] + b + 1ll * cntC * c + 1ll * (r - l + 1 - 1ll * len * cntC) * a << '\n'; mini(dp[l][r], dp[l][k] + b + 1ll * cntC * c + 1ll * (r - l + 1 - 1ll * len * cntC) * a); } } } cout << dp[3][5] << '\n'; cout << dp[3][8] << '\n'; cout << dp[1][n]; } } namespace sub5 { bool check() { return n <= 1e3; } const int N = 2e3 + 5e2 + 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]; vector<int> val; vector<int> lst[N * N]; vector<pair<int, int>> adj[N]; int nxt[N][N]; void solve() { 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++) { val.emplace_back(get(l, r)); } } sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin()); auto Rank = [&](int x) { return lower_bound(val.begin(), val.end(), x) - val.begin(); }; for(int i = 0; i < val.size(); i++) lst[i].emplace_back(n + 1); for(int l = n; l > 0; l--) { for(int r = l; r <= n; r++) { int H = Rank(get(l, r)); int lo = 0, hi = lst[H].size() - 1; while(lo <= hi) { int mid = (lo + hi) >> 1; if(lst[H][mid] > r) { nxt[l][r - l + 1] = lst[H][mid]; lo = mid + 1; } else hi = mid - 1; } lst[H].emplace_back(l); } } for(int l = n; l > 0; l--) { dp[l][l] = a; for(int r = l; r <= n; r++) adj[r].clear(); for(int len = 1; l + len - 1 <= n; len++) { int cntC = 0, r = l; while(r + len - 1 <= n) { cntC++; if(r > l) adj[r + len - 1].emplace_back(len, cntC); r = nxt[r][len]; } } for(int r = l + 1; r <= n; r++) { dp[l][r] = dp[l + 1][r] + a; mini(dp[l][r], dp[l][r - 1] + a); for(auto[len, cntC] : adj[r]) { mini(dp[l][r], dp[l][l + len - 1] + b + 1ll * cntC * c + (r - l + 1 - 1ll * len * cntC) * a); } } } cout << dp[1][n]; } } int main() { fastio; local(); cin >> n >> s >> a >> b >> c; //sub4::solve(); cout << '\n'; sub5::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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~