Submission #1248507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248507		avighna	Copy and Paste 3 (JOI22_copypaste3)	C++20	57 / 100	3098 ms	215132 KiB

copypaste3

#include <bits/stdc++.h>

const int64_t A1 = 43, A2 = 31;
const int64_t mod1 = 1e9 + 7, mod2 = 1000139249;
std::vector<int64_t> pow1, pow2;
const int64_t inf = 1e15;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n;
  std::string s;
  int a, b, c;
  std::cin >> n >> s >> a >> b >> c;

  pow1.resize(n), pow2.resize(n);
  pow1[0] = pow2[0] = 1;
  for (int i = 1; i < n; ++i) {
    pow1[i] = (pow1[i - 1] * A1) % mod1;
    pow2[i] = (pow2[i - 1] * A2) % mod2;
  }
  struct Hash {
    int64_t hash1, hash2, len;
    Hash() : hash1(0), hash2(0), len(0) {}
    Hash(int64_t hash1, int64_t hash2, int64_t len) : hash1(hash1), hash2(hash2), len(len) {}
    bool operator<(const Hash &other) const {
      if (len != other.len) {
        return len < other.len;
      }
      if (hash1 != other.hash1) {
        return hash1 < other.hash1;
      }
      return hash2 < other.hash2;
    }
    bool operator==(const Hash &other) {
      return hash1 == other.hash1 and hash2 == other.hash2 and len == other.len;
    }
    void append(char c) {
      hash1 = (hash1 + pow1[len++] * c) % mod1;
      hash2 = (hash2 + pow2[len++] * c) % mod2;
    }
  };

  std::vector hashes(n, std::vector<Hash>(n + 1));
  std::map<Hash, std::vector<int>> positions;
  for (int i = 0; i < n; ++i) {
    Hash cur_hash;
    for (int j = i; j < n; ++j) {
      cur_hash.append(s[j]);
      positions[hashes[i][j + 1] = cur_hash].push_back(i);
    }
  }

  std::vector dp(n, std::vector<int64_t>(n + 1, inf));
  for (int i = 0; i < n; ++i) {
    dp[i][i + 1] = a + b;
  }
  for (int64_t len = 1; len <= n; ++len) {
    for (int l = 0; l + len <= n; ++l) {
      int r = l + len;
      if (l > 0) {
        dp[l - 1][r] = std::min(dp[l - 1][r], dp[l][r] + a);
      }
      if (r < n) {
        dp[l][r + 1] = std::min(dp[l][r + 1], dp[l][r] + a);
      }
      if (c > a * len) {
        continue;
      }
      Hash hash = hashes[l][r];
      auto it = std::lower_bound(positions[hash].begin(), positions[hash].end(), l);
      int64_t cnt = 1;
      while (it != positions[hash].end() and *it + len <= n) {
        dp[l][*it + len] = std::min(dp[l][*it + len], dp[l][r] + cnt * c + (*it + len - l - len * cnt) * a + b);
        it = std::lower_bound(positions[hash].begin(), positions[hash].end(), *it + len);
        cnt += 1;
      }
    }
  }

  std::cout << dp[0][n] - b << '\n';
}

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