Submission #1252740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252740		LucaLucaM	Copy and Paste 3 (JOI22_copypaste3)	C++20	62 / 100	3094 ms	49556 KiB

copypaste3

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

#define int ll

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

const ll INF = 1e18;

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

  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] + (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: 0 / 38