This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;
template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;
const int N = 2510;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dp[N][N];
int nxt[N][N];
int pref[N];
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n;
ll a, b, c;
string s;
cin >> n >> s >> a >> b >> c;
for (int i = 0; i < n; ++i) {
fill(pref, pref + n, 0);
pref[i] = n - i;
int zbegin = 0, zend = 0;
for (int j = i + 1; j < n; ++j) {
if (zend > j) {
pref[j] = min(zend - j, pref[i + j - zbegin]);
}
while (s[j + pref[j]] == s[i + pref[j]]) {
++pref[j];
}
if (zend < j + pref[j]) {
zbegin = j;
zend = j + pref[j];
}
}
int mx = 1;
for (int j = i + 1; j <= n; ++j) {
nxt[i][j] = n;
for (int h = mx; mx <= min(j - i, pref[j]); ++mx) {
nxt[i][i + h] = j;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
dp[i][j] = (j - i) * a;
}
}
for (int len = 1; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int at = nxt[i][i + len];
ll curr = dp[i][i + len] + b + 2 * c + (at - i - len) * a;
while (at != n) {
dp[i][at + len] = min(curr, dp[i][at + len]);
int prv = at;
at = nxt[at][at + len];
curr += c + (at - prv - len) * a;
}
}
// if (!(len & (len - 1))) {
for (int len2 = len; len2 <= n; ++len2) {
for (int i = 0; i <= n - len2; ++i) {
dp[i][i + len2] = min({dp[i][i + len2], dp[i][i + len2 - 1] + a, dp[i + 1][i + len2] + a});
}
}
// }
}
// for (int len2 = 2; len2 <= n; ++len2) {
// for (int i = 0; i <= n - len2; ++i) {
// dp[i][i + len2] = min({dp[i][i + len2], dp[i][i + len2 - 1] + a, dp[i + 1][i + len2] + a});
// }
// }
cout << dp[0][n];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |