이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <map>
using namespace std;
long long int c[3005], p[3005], f[3005][3005], g[3005][3005], mod = 1e9 + 7, b = 177013;
long long int check(int i, int j) {
return (c[j] - c[i - 1] * p[j - i + 1] % mod + mod) % mod;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
long long int n, x, y, z;
string s;
cin >> n >> s >> x >> y >> z;
s = " " + s;
p[0] = 1;
for (int i = 1; i <= n; i++) {
c[i] = (c[i - 1] * b + s[i] - 'a' + 1) % mod;
p[i] = p[i - 1] * b % mod;
}
for (int d = 1; d <= n; d++) {
map<long long int, int> m;
for (int i = n - d + 1; i >= 1; i--) {
int j = i + d - 1;
g[i][j] = 1e18;
long long int h = check(i, j);
if (m.count(h)) f[i][j] = m[h];
else f[i][j] = 0;
if (j + d - 1 <= n) m[check(j, j + d - 1)] = j;
}
}
for (int d = 1; d <= n; d++) {
for (int i = 1; i <= n - d + 1; i++) {
int j = i + d - 1;
g[i][j] = min(g[i][j], x * d);
g[i][j] = min(g[i][j], min(g[i + 1][j], g[i][j - 1]) + x);
int h = i, l = 1;
while (1) {
h = f[h][h + d - 1];
if (h == 0) break;
int k = h + d - 1;
l++;
g[i][k] = min(g[i][k], g[i][j] + y + x * (k - i + 1 - l * d) + l * z);
}
}
}
cout << g[1][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... |