#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define fi first
#define se second
const ll mod = 1707726299;
const ll maxN = 2505;
const ll maxNr = 2500;
const ll INF = 1e18;
void maddto(ll &x, ll y) {x += y; x %= mod;}
ll msub(ll x, ll y) {x -= y; while (x < 0) x += mod; x %= mod; return x;}
ll mmul(ll x, ll y) {x *= y; x %= mod; return x;}
void chmin(ll &x, ll y) {x = min(x, y);}
ll modexp(ll x, ll y) {
if (!x) return 0; if (!y) return 1;
ll t = modexp(x, y >> 1);
return mmul(t, mmul(t, (y & 1) ? x : 1));
}
ll A, B, C, N;
char S[maxN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> uid(1e5, 2e5);
ll key = uid(rng), invkey = modexp(key, mod-2);
ll kpow[maxN], invkpow[maxN], hsh[maxN];
ll dp[maxN][maxN], nxt[maxN][maxN];
void precomp() {
key = rng();
invkey = modexp(key, mod-2);
kpow[0] = invkpow[0] = 1;
for (ll i = 1; i <= maxNr; i++) {
kpow[i] = mmul(kpow[i-1], key);
invkpow[i] = mmul(invkpow[i-1], invkey);
}
}
void hashS() {
for (ll i = 1; i <= N; i++) {
hsh[i] = mmul(S[i], kpow[i]);
maddto(hsh[i], hsh[i-1]);
}
}
ll getHash(ll l, ll r) {
ll ret = msub(hsh[r], hsh[l-1]);
return mmul(ret, invkpow[l-1]);
}
int main() {
precomp();
scanf("%lld %lld %lld", &A, &B, &C);
S[0] = '#';
scanf("%s", S + 1);
N = strlen(S) - 1;
hashS();
// compute nxt[l][r] for each possible substring length
memset(nxt, -1, sizeof(nxt));
for (ll len = 1; len < N; len++) {
vector<pll> hashes = {{-1, -1}};
for (ll st = 1; st <= N-len+1; st++) {
hashes.push_back({getHash(st, st+len-1), st});
}
sort(hashes.begin(), hashes.end());
/*
for (auto H : hashes) {
printf("{%lld, %lld} ", H.fi, H.se);
}
cout << '\n';
*/
deque<ll> pending;
for (ll i = 1; i < hashes.size(); i++) {
if (hashes[i].fi != hashes[i-1].fi) {
pending.clear();
}
while (!pending.empty()) {
if (pending.front() <= hashes[i].se - len) {
nxt[pending.front()][pending.front()+len-1] = hashes[i].se;
pending.pop_front();
} else break;
}
pending.push_back(hashes[i].se);
}
}
/*
for (ll l = 1; l <= N; l++) {
for (ll r = l; r <= N; r++) {
printf("nxt[%lld][%lld] = %lld\n", l, r, nxt[l][r]);
}
}
*/
// Calculate DP
for (auto &i : dp) {
for (auto &j : i) {
j = INF;
}
}
// Base case
for (ll i = 1; i < N; i++) {
dp[i][i] = A + B;
}
// Transition
for (ll len = 1; len < N; len++) {
for (ll l = 1; l <= N-len+1; l++) {
ll r = l+len-1;
// Type S[l-1]
if (l > 1) {
chmin(dp[l-1][r], dp[l][r] + A);
}
// Type S[r+1]
if (r < N) {
chmin(dp[l][r+1], dp[l][r] + A);
}
// Paste next occurences of S[l..r]
ll cur = l, pastes = 1;
while (nxt[cur][cur+len-1] != -1) {
cur = nxt[cur][cur+len-1];
pastes++;
chmin(
dp[l][cur+len-1],
dp[l][r] + 1ll * pastes * C + 1ll * (cur+len-l - 1ll * len * pastes) * A + B
);
}
}
}
printf("%lld\n", dp[1][N] - B);
}
Compilation message
copypaste3.cpp: In function 'll modexp(ll, ll)':
copypaste3.cpp:22:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
22 | if (!x) return 0; if (!y) return 1;
| ^~
copypaste3.cpp:22:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
22 | if (!x) return 0; if (!y) return 1;
| ^~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:85:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (ll i = 1; i < hashes.size(); i++) {
| ~~^~~~~~~~~~~~~~~
copypaste3.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%lld %lld %lld", &A, &B, &C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%s", S + 1);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
98508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
