제출 #1252737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252737		LucaLucaM	Copy and Paste 3 (JOI22_copypaste3)	C++20	0 / 100	0 ms	328 KiB

copypaste3

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

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

const ll INF = 1e18;

int 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;
  }

  for (int len = 1; len <= n; len++) {
    std::vector<int> next(n + 1, -1);
    for (int i = 1; i + len - 1 <= n; i++)  {
      int j = i + len;
      while (j + len - 1 <= n && s.substr(i, len) != s.substr(j, len)) {
        j++;
      }
      if (j + len - 1 <= n) {
        next[i] = j;
      } else {
        next[i] = -1;
      }
    }
    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] + (cnt + 1) * C + (ll) (j - i - cnt * len) * A);
        }
      }
    }
  }
  
  std::cout << dp[1][n];
  
  return 0;
}

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