#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#ifndef LOCAL
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 mt(time(0));
void solve();
void init();
int32_t main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cout << fixed << setprecision(30);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
const int N = 2525, mod = 1000000321, p = 31;
ll dp[N][N];
int to[N][N], nw[N][N], hsh[N], pdeg[N], pinv[N];
vector<pair<int, int>> upd[N];
int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a, int b) {
return a >= b ? a - b : a - b + mod;
}
int mul(int a, int b) {
return 1ll * a * b % mod;
}
int bin_pow(int a, int x) {
int res = 1;
while (x) {
if (x & 1) {
res = mul(res, a);
}
a = mul(a, a);
x >>= 1;
}
return res;
}
int inv(int a) {
return bin_pow(a, mod - 2);
}
void init() {
pdeg[0] = 1;
pdeg[1] = p;
pinv[0] = 1;
pinv[1] = inv(p);
for (int i = 2; i < N; i++) {
pdeg[i] = mul(pdeg[i - 1], p);
pinv[i] = mul(pinv[i - 1], pinv[1]);
}
}
int get_hash(int l, int r) {
return mul(sub(hsh[r + 1], hsh[l]), pinv[l]);
}
struct segment_tree {
vector<ll> st;
int size;
segment_tree(int sz = N) {
st.resize(2 * sz, 0);
size = sz;
}
void add(int i, ll v) {
i += size;
st[i] += v;
i >>= 1;
while (i) {
st[i] = min(st[2 * i], st[2 * i + 1]);
i >>= 1;
}
}
ll get_min(int l, int r) {
l += size;
r += size;
ll res = INT64_MAX;
while (l <= r) {
if (l & 1) {
res = min(res, st[l++]);
}
if (~r & 1) {
res = min(res, st[r--]);
}
l >>= 1;
r >>= 1;
}
return res;
}
};
segment_tree st[N];
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int a, b, c;
cin >> a >> b >> c;
hsh[0] = 0;
for (int i = 0; i < n; i++) {
hsh[i + 1] = add(hsh[i], mul(s[i] - 'a' + 1, pdeg[i]));
}
for (int l = 0; l < n; l++) {
unordered_map<int, int> mp;
for (int i = 0; i < n - l; i++) {
int j = i + l;
int nw = get_hash(i, j);
if (mp.find(nw) == mp.end()) {
to[i][j] = -1;
} else {
to[i][j] = mp[nw];
}
if (i >= l) {
mp[get_hash(i - l, i)] = i - l;
}
}
}
for (int i = 0; i < n; i++) {
dp[i][i] = a;
// save[i][i] = b + c;
st[i].add(i, b + c);
nw[i][i] = to[i][i];
if (to[i][i] != -1) {
upd[i - to[i][i]].emplace_back(i, i);
}
}
for (int l = 1; l < n; l++) {
for (auto [i, j] : upd[l]) {
int nxt = to[nw[i][j]][nw[i][j] + j - i];
nw[i][j] = nxt;
if (nxt >= 0) {
upd[j - nxt].emplace_back(i, j);
}
// save[j][i] += b - 1ll * (j - i + 1) * a;
st[j].add(i, b - 1ll * (j - i + 1) * a);
}
for (int i = 0; i < n - l; i++) {
int j = i + l;
dp[i][j] = 1ll * (j - i + 1) * a + min(0ll, st[j].get_min(i + 1, j));
st[j].add(i, dp[i][j] + b + c - 1ll * (j - i + 1) * a);
nw[i][j] = to[i][j];
if (nw[i][j] != -1) {
upd[j - nw[i][j]].emplace_back(i, j);
}
}
}
cout << dp[0][n - 1] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
106444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
106588 KB |
Output is correct |
| 2 |
Correct |
39 ms |
106584 KB |
Output is correct |
| 3 |
Incorrect |
1263 ms |
268608 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
106444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
106444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
106444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
106444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
