#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 2505;
const ll inf = 1e18;
ll mod = 1e9 + 7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rr(ll l, ll r){
return(uniform_int_distribution<ll>(l, r)(rng));
}
ll n, a, b, c;
string s;
ll dp[mxn + 1][mxn + 1], hsh[mxn + 1], pw[mxn + 1];
int nxt[mxn + 1];
struct HASH{
ll base, mod;
ll pw[2505], hsh[2505];
void init(string s, ll _base, ll _mod){
base = _base; mod = _mod;
pw[0] = 1;
for(int i = 1; i <= n; i++){
pw[i] = (pw[i - 1] * base) % mod;
}
for(int i = 1; i <= n; i++){
hsh[i] = (hsh[i - 1] * base + (s[i - 1] - 'a' + 1)) % mod;
}
}
ll gethsh(int l, int r){
return((hsh[r] - hsh[l - 1] * pw[r - l + 1] + mod * mod) % mod);
}
};
HASH h1, h2;
void ckmin(ll &a, ll b){
a = min(a, b);
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s >> a >> b >> c;
h1.init(s, 171, rr(1e8, 1e9)); h2.init(s, 171, rr(1e8, 1e9)); mod = rr(1e9, 1e9 + 200)
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
dp[i][j] = inf;
}
}
for(int len = 1; len <= n; len++){
vt<pii>comp;
for(int j = 1; j + len - 1 <= n; j++){
nxt[j] = -1;
comp.pb(make_pair((h1.gethsh(j, j + len - 1) * h2.gethsh(j, j + len - 1)) % mod, j));
}
sort(comp.begin(), comp.end());
for(int i = 0; i < sz(comp);){
int r = i;
while(r < sz(comp) && comp[r].first == comp[i].first)r++;
int rp = i;
for(int j = i; j < r; j++){
while(rp < r && comp[rp].second < comp[j].second + len){
rp++;
}
if(rp == r)nxt[comp[j].second] = -1;
else nxt[comp[j].second] = comp[rp].second;
}
i = r;
}
for(int i = 1; i + len - 1 <= n; i++){
int l = i, r = i + len - 1;
ckmin(dp[l][r], dp[l + 1][r] + a); ckmin(dp[l][r], dp[l][r - 1] + a);
int idl = l, cnt = 1;
while(nxt[idl] != -1){
idl = nxt[idl];
cnt++;
int nwr = idl + len - 1;
ckmin(dp[l][nwr], dp[l][r] + b + c * cnt + a * (nwr - l + 1 - len * cnt));
}
}
}
cout << dp[1][n];
return(0);
}
Compilation message
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:59:91: error: expected ';' before 'for'
59 | h1.init(s, 171, rr(1e8, 1e9)); h2.init(s, 171, rr(1e8, 1e9)); mod = rr(1e9, 1e9 + 200)
| ^
| ;
60 | for(int i = 1; i <= n; i++){
| ~~~
copypaste3.cpp:60:20: error: 'i' was not declared in this scope
60 | for(int i = 1; i <= n; i++){
| ^
