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>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
void ckmin(LL& a, LL b) {
if(a > b) {
a = b;
}
}
const int N = 2503;
const int B = 311;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, a, b, c, g[N][N];
char s[N];
LL f[N][N], dp[N];
ULL h[N], pw[N];
ULL get(int l, int r) {
return h[r] - h[l] * pw[r - l];
}
int main() {
scanf("%d %s %d %d %d", &n, s, &a, &b, &c);
h[0] = 0;
pw[0] = 1;
for(int i = 0; i < n; ++i) {
h[i + 1] = h[i] * B + s[i];
pw[i + 1] = pw[i] * B;
}
for(int i = n; i--; ) {
for(int j = i + 1; j <= n; ++j) {
g[i][j] = (j + j - i <= n && get(i, j) == get(j, j + j - i)) ? g[j][j + j - i] + 1 : 1;
}
}
for(int i = 0; i < n; ++i) {
f[i][i + 1] = a + b;
}
for(int L = 2; L <= n; ++L) {
for(int i = 0, j = L; j <= n; ++i, ++j) {
f[i][j] = (LL)a * L;
for(int l = i; l < j; ++l) {
for(int r = l + 1; r <= j; ++r) {
dp[i] = 0;
for(int k = i + 1; k <= j; ++k) {
dp[k] = INF;
}
for(int k = i; k < j; ++k) {
ckmin(dp[k + 1], dp[k] + a);
if(k + r - l <= j && get(l, r) == get(k, k + r - l)) ckmin(dp[k + r - l], dp[k] + c);
}
f[i][j] = min(f[i][j], f[l][r] + dp[j]);
}
}
f[i][j] += b;
}
}
printf("%lld", f[0][n] - b);
return 0;
}
Compilation message (stderr)
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%d %s %d %d %d", &n, s, &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |