Submission #1022583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022583		avighna	Copy and Paste 3 (JOI22_copypaste3)	C++17	20 / 100	3086 ms	459088 KiB

copypaste3

#include <bits/stdc++.h>

typedef long long ll;

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

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

  if (std::count(s.begin(), s.end(), 'a') == n) {
    std::vector<std::vector<ll>> dp(n + 1, std::vector<ll>(n + 1));
    // dp[i][j] = the minimum cost to match n - i a's if there are j a's in the
    // clipboard

    /*
    dp[i][j] = min{
      dp[i + 1][j] + a,
      dp[i + j][j] + c (j != 0),
      dp[0][i] + b (i > j)
    }
    */
    for (ll j = n - 1; j >= 0; --j) {
      for (ll i = n - 1; i >= 0; --i) {
        dp[i][j] = dp[i + 1][j] + a;
        if (j != 0 and i + j <= n) {
          dp[i][j] = std::min(dp[i][j], dp[i + j][j] + c);
        }
        if (i > j) {
          dp[i][j] = std::min(dp[i][j], dp[0][i] + b);
        }
      }
    }

    std::cout << dp[0][0] << "\n";
    return 0;
  }

  std::vector<std::vector<std::vector<std::vector<ll>>>> dp(
      n + 1, std::vector<std::vector<std::vector<ll>>>(
                 n + 1, std::vector<std::vector<ll>>(
                            n + 1, std::vector<ll>(n + 1, 1e15))));
  // dp[x_beg][x_len][y_beg][y_len] => dp[i][j][k][l] = the minimum cost to
  // match if the current x is (i, j) and the current y is (k, l)
  for (ll i = 0; i <= n; ++i) {
    for (ll j = 0; j <= n; ++j) {
      dp[0][n][i][j] = 0;
    }
  }

  auto substring = [&](ll _i, ll len) {
    std::string ans;
    for (ll i = 0; i < len and i + _i < n; ++i) {
      ans.push_back(s[i + _i]);
    }
    return ans;
  };

  /*
  dp[i][j][k][l] = min{
    dp[i][j + 1][k][l] + a,
    dp[i][j + l][k][l] + c (iff the string matches),
    dp[0][0][i][j] + b (if the pair (i, j) > (k, l))
  }
  */
  for (ll l = n - 1; l >= 0; --l) {
    for (ll k = n - 1; k >= 0; --k) {
      for (ll j = n - 1; j >= 0; --j) {
        for (ll i = n - 1; i >= 0; --i) {
          dp[i][j][k][l] = dp[i][j + 1][k][l] + a;
          if (j == 0) {
            for (ll m = 0; m < n; ++m) {
              dp[i][j][k][l] = std::min(dp[i][j][k][l], dp[m][1][k][l] + a);
            }
          }
          if (l != 0 and j + l <= n - i and
              substring(i, j) + substring(k, l) == substring(i, j + l)) {
            dp[i][j][k][l] = std::min(dp[i][j][k][l], dp[i][j + l][k][l] + c);
          }
          if (i > k or (i == k and j > l)) {
            dp[i][j][k][l] = std::min(dp[i][j][k][l], dp[0][0][i][j] + b);
          }
        }
      }
    }
  }

  std::cout << dp[0][0][0][0] << "\n";
}

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