Submission #1022549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022549		avighna	Copy and Paste 3 (JOI22_copypaste3)	C++17	5 / 100	69 ms	49488 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;

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

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