結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-08 23:53:16 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,829 bytes |
コンパイル時間 | 2,956 ms |
コンパイル使用メモリ | 123,116 KB |
最終ジャッジ日時 | 2025-01-17 14:45:44 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 WA * 7 |
ソースコード
#line 1 "main.cpp"/*** @title Template*/#include <iostream>#include <algorithm>#include <utility>#include <numeric>#include <vector>#include <array>#include <cassert>#include <map>#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"class range {struct iter {std::size_t itr;constexpr iter(std::size_t pos) noexcept: itr(pos) { }constexpr void operator ++ () noexcept { ++itr; }constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }constexpr std::size_t operator * () const noexcept { return itr; }};struct reviter {std::size_t itr;constexpr reviter(std::size_t pos) noexcept: itr(pos) { }constexpr void operator ++ () noexcept { --itr; }constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }constexpr std::size_t operator * () const noexcept { return itr; }};const iter first, last;public:constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }constexpr iter begin() const noexcept { return first; }constexpr iter end() const noexcept { return last; }constexpr reviter rbegin() const noexcept { return reviter(*last - 1); }constexpr reviter rend() const noexcept { return reviter(*first - 1); }};/*** @title Range*/#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/chmin_chmax.cpp"template <class T, class U>constexpr bool chmin(T &lhs, const U &rhs) {if (lhs > rhs) { lhs = rhs; return true; }return false;}template <class T, class U>constexpr bool chmax(T &lhs, const U &rhs) {if (lhs < rhs) { lhs = rhs; return true; }return false;}/*** @title Chmin/Chmax*/#line 17 "main.cpp"using i32 = std::int32_t;using i64 = std::int64_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using isize = std::ptrdiff_t;using usize = std::size_t;constexpr i32 inf32 = (u32) ~0 >> 2;constexpr i64 inf64 = (u64) ~0 >> 2;template <class T>using Vec = std::vector<T>;int main() {usize N;u64 M, P;std::cin >> N >> M >> P;Vec<u64> A(N);for (auto &x: A) {std::cin >> x;}const auto Max = *std::max_element(A.begin(), A.end());if (Max > M) {std::cout << 1 << '\n';return 0;}std::map<usize, u64> map;for (auto x: A) {usize cnt = 1;while (x % P == 0) {x /= P;}chmax(map[cnt], x);}Vec<u64> dp(1000);dp[0] = 1;for (auto i: range(0, dp.size())) {if (dp[i] > M) {std::cout << i << '\n';return 0;}for (const auto [c, g]: map) {if (i + c < dp.size()) {chmax(dp[i + c], dp[i] * g);}}}std::cout << -1 << '\n';return 0;}