Submission #1198767

#TimeUsernameProblemLanguageResultExecution timeMemory
1198767RaresFelixCopy and Paste 3 (JOI22_copypaste3)C++20
25 / 100
3097 ms26800 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; const ll MOD2 = 1e9 + 9; ll lpow(ll v, ll e, ll MOD) { return !e ? 1 : (e & 1) ? lpow(v * v % MOD, e >> 1, MOD) * v % MOD : lpow(v * v % MOD, e >> 1, MOD); } ll inv(ll v, ll MOD) { return lpow(v, MOD - 2, MOD); } struct hshuri { ///TODO: doua moduri string s; int n, inv29_1, inv29_2; vi V1, V2; hshuri(string s0) : s(s0), n(s0.size()), V1(n, 0), V2(n, 0) { for(int i = 0; i < n; ++i) { V1[i] = V2[i] = s[i] - 'a' + 1; if(i) { V1[i] = (V1[i - 1] * 29 + V1[i]) % MOD1; V2[i] = (V2[i - 1] * 29 + V2[i]) % MOD2; } } inv29_1 = inv(29, MOD1); inv29_2 = inv(29, MOD2); } pl operator()(int st, int dr) { ll re1 = V1[dr], re2 = V2[dr]; if(st) { re1 = (re1 - V1[st - 1] * lpow(29, dr - st + 1, MOD1) % MOD1 + MOD1) % MOD1; re2 = (re2 - V2[st - 1] * lpow(29, dr - st + 1, MOD2) % MOD2 + MOD2) % MOD2; } // for(int j = st; j <= dr; ++j) { // cout << s[j]; // } // cout << " " << re1 << "\n"; return {re1, re2}; } }; 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<pair<pl, int> > 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; vi S, Urm(dr - st + 1, -1); for(int j = st; j <= dr; ++j) S.push_back(Ord[j].second); sort(S.begin(), S.end()); { int p = 0; for(int i = 0; i < (int)S.size(); ++i) { while(p + 1 < S.size() && S[p] - S[i] < len) ++p; if(S[p] - S[i] < len) break; Urm[i] = p; } } for(int i = 0; i < (int)S.size(); ++i) { int st0 = S[i], p = S[i], id = i; int cost0 = b + DP[p][p + len - 1]; /// cost to start int cost_cur = c; int vmax = S.back(); while(p < n) { //printf("Dau update la (%d...%d) cu %d + %d din (%d %d)\n", p, p, cost_cur, cost0, p, p); DP[st0][p + len - 1] = min(DP[st0][p + len - 1], cost_cur + cost0); if(Urm[id] == -1) break; cost_cur += c + a * (S[Urm[id]] - p - len); id = Urm[id]; p = S[id]; } } } // 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...