Submission #998174

#TimeUsernameProblemLanguageResultExecution timeMemory
998174abczzCopy and Paste 3 (JOI22_copypaste3)C++17
62 / 100
217 ms132000 KiB
#include <iostream> #include <vector> #include <array> #include <unordered_map> #define ll long long using namespace std; string S; const ll M = 1e9 + 7; unordered_map <ll, ll> mp; ll n, a, b, c, s, base = 30, p, X[2500][2500], dp[2500][2500], nx[2500][2500]; int main() { cin.tie(0); ios::sync_with_stdio(0); cin >> n >> S >> a >> b >> c; for (int i=0; i<n; ++i) { s = 0, p = 1; for (int j=i; j<n; ++j) { (s += (S[j]-'a'+1) * p % M) %= M; (p *= base) %= M; X[i][j] = s; } } for (int len=0; len<n; ++len) { mp.clear(); for (int i=n-len-1; i>=0; --i) { if (i+2*len+1 < n) { mp[X[i+len+1][i+2*len+1]] = i+len+1; } if (mp.count(X[i][i+len])) nx[i][i+len] = mp[X[i][i+len]]; else nx[i][i+len] = -1; } for (int i=0; i+len<n; ++i) { if (len) { dp[i][i+len] = min(dp[i][i+len], min(dp[i][i+len-1], dp[i+1][i+len])); } s = 0; int j = i; while (true) { int k = nx[j][j+len]; ++s; if (k == -1) break; dp[i][k+len] = min(dp[i][k+len], dp[i][i+len] + b + (s+1) * c - (s * (len+1) * a)); j = k; } } } cout << a*n + dp[0][n-1] << '\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...