Submission #1248504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248504		avighna	Copy and Paste 3 (JOI22_copypaste3)	C++20	30 / 100	2137 ms	116248 KiB

copypaste3

#include <iostream>
#include <map>
#include <vector>

const int64_t A = 37;
const int64_t mod = 1e9 + 7;
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;

  std::vector hashes(n, std::vector<int64_t>(n + 1));
  std::map<int64_t, std::vector<int>> positions;
  for (int i = 0; i < n; ++i) {
    int64_t cur_hash = 0;
    for (int j = i; j < n; ++j) {
      positions[hashes[i][j + 1] = cur_hash = ((cur_hash * A) % mod + s[j]) % mod].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;
      }
      int64_t 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: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38