Submission #951791

#TimeUsernameProblemLanguageResultExecution timeMemory
951791EJIC_B_KEDAXCopy and Paste 3 (JOI22_copypaste3)C++17
57 / 100
3068 ms366464 KiB
#ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #ifndef LOCAL // #pragma GCC optimize("O3") // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt") #endif using namespace std; using ll = long long; using ld = long double; #define x first #define y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() mt19937_64 mt(time(0)); void solve(); void init(); int32_t main() { #ifndef LOCAL cin.tie(nullptr)->sync_with_stdio(false); #endif cout << fixed << setprecision(30); init(); int t = 1; // cin >> t; while (t--) { solve(); } } const int N = 2525, mod = 1000000321, p = 31; ll dp[N][N]; int to[N][N], nw[N][N], hsh[N], pdeg[N], pinv[N]; vector<pair<int, int>> upd[N]; int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; } int sub(int a, int b) { return a >= b ? a - b : a - b + mod; } int mul(int a, int b) { return 1ll * a * b % mod; } int bin_pow(int a, int x) { int res = 1; while (x) { if (x & 1) { res = mul(res, a); } a = mul(a, a); x >>= 1; } return res; } int inv(int a) { return bin_pow(a, mod - 2); } void init() { pdeg[0] = 1; pdeg[1] = p; pinv[0] = 1; pinv[1] = inv(p); for (int i = 2; i < N; i++) { pdeg[i] = mul(pdeg[i - 1], p); pinv[i] = mul(pinv[i - 1], pinv[1]); } } int get_hash(int l, int r) { return mul(sub(hsh[r + 1], hsh[l]), pinv[l]); } struct segment_tree { vector<ll> st; int size; segment_tree(int sz = N) { st.resize(2 * sz, 0); size = sz; } void add(int i, ll v) { i += size; st[i] += v; i >>= 1; while (i) { st[i] = min(st[2 * i], st[2 * i + 1]); i >>= 1; } } ll get_min(int l, int r) { l += size; r += size; ll res = INT64_MAX; while (l <= r) { if (l & 1) { res = min(res, st[l++]); } if (~r & 1) { res = min(res, st[r--]); } l >>= 1; r >>= 1; } return res; } }; segment_tree st[N]; void solve() { int n; cin >> n; string s; cin >> s; int a, b, c; cin >> a >> b >> c; hsh[0] = 0; for (int i = 0; i < n; i++) { hsh[i + 1] = add(hsh[i], mul(s[i] - 'a' + 1, pdeg[i])); upd[i].reserve(40 * N); } for (int l = 0; l < n; l++) { unordered_map<int, int> mp; for (int i = 0; i < n - l; i++) { int j = i + l; int nw = get_hash(i, j); if (mp.find(nw) == mp.end()) { to[i][j] = -1; } else { to[i][j] = mp[nw]; } if (i >= l) { mp[get_hash(i - l, i)] = i - l; } } } for (int i = 0; i < n; i++) { dp[i][i] = a; // save[i][i] = b + c; st[i].add(i, b + c); nw[i][i] = to[i][i]; if (to[i][i] != -1) { upd[i - to[i][i]].emplace_back(i, i); } } for (int l = 1; l < n; l++) { assert(upd[l].size() <= 40 * N); for (auto [i, j] : upd[l]) { int nxt = to[nw[i][j]][nw[i][j] + j - i]; nw[i][j] = nxt; if (nxt >= 0) { upd[j - nxt].emplace_back(i, j); } // save[j][i] += b - 1ll * (j - i + 1) * a; st[j].add(i, c - 1ll * (j - i + 1) * a); } for (int i = 0; i < n - l; i++) { int j = i + l; dp[i][j] = min(1ll * (j - i + 1) * a + min(0ll, st[j].get_min(i + 1, j)), dp[i][j - 1] + a); st[j].add(i, dp[i][j] + b + c - 1ll * (j - i + 1) * a); nw[i][j] = to[i][j]; if (nw[i][j] != -1) { upd[j - nw[i][j]].emplace_back(i, j); } } } // cout << to[3][3] << '\n'; // for (int i = 0; i < n; i++) { // for (int j = i; j < n; j++) { // cout << dp[i][j] << ' '; // } // cout << '\n'; // } cout << 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...