Submission #1252767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252767		LucaLucaM	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	517 ms	49888 KiB

copypaste3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#include <random>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const ll INF = 1e18;

std::mt19937 rng(123);

std::map<std::pair<int, int>, std::vector<int>> where;

struct stringHash {
  std::vector<int> pref;
  std::vector<int> value;
  std::vector<int> p;

  const int mod = 1e9 + 7;
  const int B = 103;
  
  int n;

  void init(std::string s) {
    n = (int) s.size();
    pref.resize(n + 1, 0);
    p.resize(n + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
      p[i] = (ll) p[i - 1] * B % mod;
    }
    value.resize(256);
    for (int &x : value) {
      x = rng() % mod;
    }
    for (int i = 1; i <= n; i++) {
      pref[i] = pref[i - 1] + (ll) value[s[i]] * p[i] % mod;
      pref[i] %= mod;
    }
  }

  int queryHash(int l, int r) {
    int ret = pref[r] - pref[l - 1];
    if (ret < 0) {
      ret += mod;
    }
    // teoretic trebuie sa inmultesc cu B^-l (devastator) 
    // dar o sa inmultesc cu B^(n-l) (asta e mega smart)
    return (ll) ret * p[n - l] % mod;
  }

};

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  std::string s;
  std::cin >> s;

  s = '$' + s;

  int A, B, C;
  std::cin >> A >> B >> C;

  std::vector<std::vector<ll>> dp(n + 2, std::vector<ll>(n + 2, +INF));

  for (int i = 1; i <= n; i++) {
    dp[i][i - 1] = 0;
    dp[i][i] = A;
  }

  stringHash hash1, hash2;
  hash1.init(s);
  hash2.init(s);

  std::vector<int> next(n + 1, -1);

  for (int len = 1; len <= n; len++) {
    for (int i = 1; i + len - 1 <= n; i++) {
      where[{hash1.queryHash(i, i + len - 1), hash2.queryHash(i, i + len - 1)}].push_back(i);
      next[i] = -1;
    }
    for (const auto &[h, ids] : where) {
      for (int i = 0, j = 0; i < (int) ids.size(); i++) {
        while (j < (int) ids.size() && ids[j] < ids[i] + len) {
          j++;
        }
        next[ids[i]] = (j == (int) ids.size()? -1 : ids[j]);
      }
    }
    where.clear();

    for (int i = 1; i + len - 1 <= n; i++) {
      dp[i][i + len - 1] = std::min(dp[i][i + len - 1], std::min(dp[i][i + len - 2], dp[i + 1][i + len - 1]) + A);
    }
    for (int i = 1; i + len - 1 <= n; i++) {
      if (next[i] != -1) {
        int j = i;
        int cnt = 0; // de cate ori dau paste
        while (next[j] != -1) {
          j = next[j];
          cnt++;
          dp[i][j + len - 1] = std::min(dp[i][j + len - 1], B + dp[i][i + len - 1] + (ll) (cnt + 1) * C + (ll) (j - i - cnt * len) * A);
        }
      }
    }
  }
  
  std::cout << dp[1][n];
  
  return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38