結果
問題 | No.2039 Copy and Avoid |
ユーザー |
|
提出日時 | 2022-08-12 22:27:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 1,387 bytes |
コンパイル時間 | 2,560 ms |
コンパイル使用メモリ | 208,160 KB |
最終ジャッジ日時 | 2025-01-30 21:20:44 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using i64 = long long; constexpr i64 inf = 1ll << 50; int main() { i64 N, A, B; int M; std::cin >> N >> M >> A >> B; std::vector<i64> C(M); for (auto &e : C) std::cin >> e; std::sort(C.begin(), C.end()); std::map<i64, i64> dp; std::map<i64, i64> mi_d; auto calc_mi_d = [&](const i64 x) { if (mi_d.find(x) != mi_d.end()) return; for (const auto e : C) { if (e % x == 0) { mi_d[x] = e; return; } } mi_d[x] = inf; return; }; auto solve = [&](auto &&self, const i64 x) -> i64 { calc_mi_d(x); if (std::binary_search(C.begin(), C.end(), x)) return inf; if (x == 1) return 0; if (dp.find(x) != dp.end()) return dp[x]; std::vector<i64> dvs; for (i64 i = 1; i * i <= x; ++i) { if (x % i == 0) { dvs.push_back(i); dvs.push_back(x / i); } } i64 result = inf; for (const auto e : dvs) { if (e == x) continue; i64 val = self(self, e) + A * (x / e - 1); if (mi_d[e] <= x) continue; result = std::min(result, val); } return dp[x] = result + B; }; const auto ans = solve(solve, N); std::cout << (ans >= inf ? -1 : ans - B) << std::endl; }