結果
問題 |
No.2162 Copy and Paste 2
|
ユーザー |
|
提出日時 | 2025-01-03 15:56:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 7,000 ms |
コード長 | 1,556 bytes |
コンパイル時間 | 2,245 ms |
コンパイル使用メモリ | 166,592 KB |
実行使用メモリ | 15,632 KB |
最終ジャッジ日時 | 2025-01-03 15:56:17 |
合計ジャッジ時間 | 4,737 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #define rep(i, j, k) for (int i = (j); i <= (k); ++i) #define per(i, j, k) for (int i = (j); i >= (k); --i) #define SZ(v) int((v).size()) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second using ll = long long; using pii = std::pair<int, int>; using pll = std::pair<ll, ll>; template<class T> void chkmn(T &x, T y) { if (y < x) x = y; } template<class T> void chkmx(T &x, T y) { if (y > x) x = y; } using namespace std; const int maxn = 2000010; int n, a[maxn], z[maxn], fa[maxn], f[maxn], p[maxn]; string s; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } int main() { // freopen("asdf.in", "r", stdin); // freopen("asdf.out", "w", stdout); cin.tie(nullptr) -> ios::sync_with_stdio(false); cin >> s, n = s.length(); rep (i, 1, n) a[i] = s[i - 1] - 'a'; rep (i, 1, n + 1) fa[i] = i; int l = 1, r = 0; rep (i, 2, n) { z[i] = max(0, min(r - i + 1, z[i - l + 1])); while (i + z[i] <= n && a[i + z[i]] == a[z[i] + 1]) z[i]++; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } rep (i, 1, n) p[i] = i; sort(p + 1, p + n + 1, [&](int x, int y) { return z[x] < z[y]; }); rep (i, 1, n) f[i] = 1e9; int pos = 1; rep (i, 1, n) { chkmn(f[i], f[i - 1] + 1); while (pos <= n && z[p[pos]] < i) fa[find(p[pos])] = find(p[pos] + 1), pos++; int cur = i, used = 0; while (cur <= n) { cur = find(cur + 1) + i - 1; if (cur > n) break; used++, chkmn(f[cur], f[i] + (cur - i) - used * (i - 1) + 1); } } cout << f[n] << '\n'; }