Submission #1061140

#TimeUsernameProblemLanguageResultExecution timeMemory
1061140thinknoexitCopy and Paste 3 (JOI22_copypaste3)C++17
100 / 100
1227 ms74292 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; char s[2505]; int qs[2505][2505]; ll dp[2505][2505]; ll A, B, C; 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'; } 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 = 1;i + j <= n;j++) { qs[i][j] = s[i] == s[i + j]; } for (int j = 1;j <= n;j++) { qs[i][j] += qs[i - 1][j]; } } 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 = 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++) { int x = l - j; if (qs[j][x] - qs[i - 1][x] == j - i + 1) { if (l - prev > k) { cnt++; prev = l; } dp[i][l] = min(dp[i][l], A * (l - i + 1 - cnt * (k + 1)) + (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...