結果
問題 | No.2162 Copy and Paste 2 |
ユーザー |
![]() |
提出日時 | 2021-08-24 23:37:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,984 ms / 7,000 ms |
コード長 | 963 bytes |
コンパイル時間 | 3,230 ms |
コンパイル使用メモリ | 224,592 KB |
最終ジャッジ日時 | 2025-01-24 01:47:35 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/string> #include <atcoder/lazysegtree> using namespace atcoder; int mymax(int a, int b) { return max(a, b); } int e() { return 0; } int main() { string S; cin >> S; int N = S.size(); vector<int> Z = z_algorithm(S); for (int i = 0; i < N; i++) { Z.at(i) = min(Z.at(i), i); } vector<vector<int>> invZ(N); set<int> st; for (int i = 0; i < N; i++) { if (Z.at(i) >= 2) { invZ.at(Z.at(i)).push_back(i); st.emplace(i); } } st.emplace(N + 1); lazy_segtree<int, mymax, e, int, mymax, mymax, e> dp(N + 1); for (int j = 2; j < N; j++) { int cnt = dp.get(j) + j - 2; int i = *st.begin() + j; while (i < N + 1) { dp.apply(i, N + 1, cnt); cnt += j - 1; i = *st.lower_bound(i) + j; } for (auto ii : invZ.at(j)) { st.erase(ii); } } int ans = N - dp.get(N); cout << ans << endl; }