Submission #1248503

#TimeUsernameProblemLanguageResultExecution timeMemory
1248503avighnaCopy and Paste 3 (JOI22_copypaste3)C++20
1 / 100
1 ms328 KiB
#include <bits/stdc++.h> const int64_t A = 37; const int64_t mod = 1e9 + 7; const int64_t inf = 1e15; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::string s; int a, b, c; std::cin >> n >> s >> a >> b >> c; std::vector hashes(n, std::vector<int64_t>(n + 1)); std::map<int64_t, std::vector<int>> positions; for (int i = 0; i < n; ++i) { int64_t cur_hash = 0; for (int j = i; j < n; ++j) { positions[hashes[i][j + 1] = cur_hash = ((cur_hash * A) % mod + s[j]) % mod].push_back(i); } } std::vector dp(n, std::vector<int64_t>(n + 1, inf)); for (int i = 0; i < n; ++i) { dp[i][i + 1] = a + b; } for (int64_t len = 1; len <= n; ++len) { for (int l = 0; l + len <= n; ++l) { int r = l + len; if (l > 0) { dp[l - 1][r] = std::min(dp[l - 1][r], dp[l][r] + a); } if (r <= n) { dp[l][r + 1] = std::min(dp[l][r + 1], dp[l][r] + a); } if (c > a * len) { continue; } int64_t hash = hashes[l][r]; auto it = std::lower_bound(positions[hash].begin(), positions[hash].end(), l); int64_t cnt = 1; while (it != positions[hash].end() and *it + len <= n) { dp[l][*it + len] = std::min(dp[l][*it + len], dp[l][r] + cnt * c + (*it + len - l - len * cnt) * a + b); it = std::lower_bound(positions[hash].begin(), positions[hash].end(), *it + len); cnt += 1; } } } std::cout << dp[0][n] - b << '\n'; }
#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...