이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
void Hollwo_Pelw();
signed main(){
#ifndef hollwo_pelw_local
if (fopen(".inp", "r"))
assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
using namespace chrono;
auto start = steady_clock::now();
#endif
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
int testcases = 1;
// cin >> testcases;
for (int test = 1; test <= testcases; test++){
// cout << "Case #" << test << ": ";
Hollwo_Pelw();
}
#ifdef hollwo_pelw_local
auto end = steady_clock::now();
cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
#define int long long
const int N = 2525, P = 31;
int n, a, b, c, dp[N][N], nxt[N];
char ch[N];
uint64_t hsh[N], f[N], pw[N];
void Hollwo_Pelw(){
cin >> n;
for (int i = 1; i <= n; i++)
cin >> ch[i];
pw[0] = 1;
for (int i = 1; i <= n; i++) {
pw[i] = pw[i - 1] * P;
hsh[i] = hsh[i - 1] * P + (ch[i] - 'a' + 1);
}
cin >> a >> b >> c;
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i <= n; i++)
dp[i + 1][i] = 0;
for (int s = 1; s <= n; s++) {
for (int l = 1, r = s; r <= n; l++, r++) {
dp[l][r] = min(dp[l][r], dp[l][r - 1] + a);
dp[l][r] = min(dp[l][r], dp[l + 1][r] + a);
f[l] = hsh[r] - hsh[l - 1] * pw[s];
}
map<uint64_t, int> lst;
for (int l = n - s + 1; l >= 1; l--) {
if (l + s <= n - s + 1)
lst[f[l + s]] = l + s;
nxt[l] = lst.count(f[l]) ? lst[f[l]] : n + 1;
}
for (int l = 1, r = s; r <= n; l++, r++) {
for (int L = l, cnt = 1; L + s - 1 <= n; L = nxt[L], cnt ++) {
dp[l][L + s - 1] = min(dp[l][L + s - 1], dp[l][r] + b + c * cnt + (L + s - l - cnt * s) * a);
}
}
}
cout << dp[1][n] << '\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... |