Submission #1198761

#TimeUsernameProblemLanguageResultExecution timeMemory
1198761RaresFelixCopy and Paste 3 (JOI22_copypaste3)C++20
25 / 100
3095 ms26696 KiB
#include <bits/stdc++.h> using namespace std; #define int ll using ll = long long; using vi = vector<int>; using vll = vector<ll>; using ii = pair<int, int>; using pl = pair<ll, ll>; const ll MOD1 = 1e9 + 7; struct hshuri { ///TODO: doua moduri string s; hshuri(string s0) : s(s0) {} ll operator()(int st, int dr) { int re = 1; for(int j = st; j <= dr; ++j) re = (re * 29 + (s[j] - 'a')) % MOD1; return re; } }; const ll INF = 1e18; signed main() { cin.tie(0); ios_base::sync_with_stdio(0); int n; string s; int a, b, c; cin >> n >> s >> a >> b >> c; vector<vi> DP(n, vi(n, INF)); hshuri HSH(s); for(int i = 0; i < n; ++i) DP[i][i] = a; for(int len = 1; len <= n; ++len) { vector<ii> Ord; for(int i = 0; i + len - 1 < n; ++i) Ord.push_back({HSH(i, i + len - 1), i}); sort(Ord.begin(), Ord.end()); for(int st = 0; st < (int)Ord.size(); ++st) { int dr = st; while(dr + 1 < (int)Ord.size() && Ord[dr + 1].first == Ord[st].first) ++dr; set<int> S; for(int j = st; j <= dr; ++j) S.insert(Ord[j].second); for(auto st0 : S) { int p = st0 + len - 1; int cost0 = b + DP[st0][p]; /// cost to start int cost_cur = c; while(p < n) { //printf("Dau update la (%d...%d) cu %d + %d din (%d %d)\n", st0, p, cost_cur, cost0, st0, p); DP[st0][p] = min(DP[st0][p], cost_cur + cost0); if(*S.rbegin() <= p) break; int urm = *S.lower_bound(p + 1); cost_cur += c + a * (urm - p - 1); p = urm + len - 1; } } } // de propagat chestii for(int i = 0; i + len < n; ++i) { DP[i][i + len] = min(DP[i][i + len], DP[i][i + len - 1] + a); DP[i][i + len] = min(DP[i][i + len], DP[i + 1][i + len] + a); } } cout << DP[0][n - 1] << "\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...