結果

問題 No.2162 Copy and Paste 2
コンテスト
ユーザー Suyi Wang
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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';
}
0