Submission #1061120

#TimeUsernameProblemLanguageResultExecution timeMemory
1061120thinknoexitCopy and Paste 3 (JOI22_copypaste3)C++17
6 / 100
7 ms2396 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const ll Base = 31; char s[2505]; ll dp[2505][2505], h[2505], pw[2505], H[2505]; ll A, B, C; ll val(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; bool ch = 1; for (int i = 1;i <= n;i++) { cin >> s[i]; ch &= s[i] == 'a'; h[i] = h[i - 1] * B + (s[i] - 'a'); pw[i] = pw[i - 1] * B; } cin >> A >> B >> C; if (ch) { vector<ll> dp(n + 2, 0); for (int i = 1;i <= n;i++) { dp[i] = dp[i - 1] + A; for (int j = 1;j < i;j++) { dp[i] = min(dp[i], (dp[j] + B) + A * (i % j) + C * (i / j)); } } cout << dp[n] << '\n'; return 0; } for (int i = 1;i <= n;i++) { for (int j = i + 1;j <= n;j++) { dp[i][j] = (j - i + 1) * A; } } for (int i = 1;i <= n;i++) { dp[i][i] = A; int cnt = 1; for (int j = i + 1;j <= n;j++) { if (s[i] == s[j]) { cnt++; dp[i][j] = min(dp[i][j], A * (j - i + 1 - cnt) + A + B + cnt * C); } } } for (int k = 1;k < n;k++) { for (int i = k + 1;i <= n;i++) { H[i] = val(i - k, i); } for (int i = 1;i <= n - k;i++) { int j = i + k; dp[i][j] = min(dp[i][j], A + dp[i + 1][j]); dp[i][j] = min(dp[i][j], dp[i][j - 1] + A); int cnt = 1, prev = j; for (int l = j + k + 1;l <= n;l++) { if (H[j] == H[l]) { if (l - prev > k) { cnt++; prev = l; } dp[i][l] = min(dp[i][l], A * (l - i + 1 - cnt * k) + (dp[i][j] + B) + cnt * C); } } } } cout << dp[1][n] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...