結果
問題 | No.1782 ManyCoins |
ユーザー |
|
提出日時 | 2021-12-07 01:05:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 2,762 bytes |
コンパイル時間 | 2,037 ms |
コンパイル使用メモリ | 206,612 KB |
最終ジャッジ日時 | 2025-01-26 06:17:24 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
// いけ!おれの信じたコード #include <bits/stdc++.h> using namespace std; // template {{{ using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define range(i, l, r) for (i64 i = (i64)(l); i < (i64)(r); (i) += 1) #define rrange(i, l, r) for (i64 i = (i64)(r) - 1; i >= (i64)(l); (i) -= 1) #define whole(f, x, ...) ([&](decltype((x)) container) { return (f)( begin(container), end(container), ## __VA_ARGS__); })(x) #define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x) #define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl constexpr i32 inf = 1001001001; constexpr i64 infll = 1001001001001001001ll; constexpr i32 dx[] = {0, -1, 1, 0, -1, 1, -1, 1}; constexpr i32 dy[] = {-1, 0, 0, 1, -1, -1, 1, 1}; struct IoSetup { IoSetup(i32 x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup; template <typename T = i64> T input() { T x; cin >> x; return x; } template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != (int)v.size() ? " " : ""); } return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; } template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); } template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); } template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } // }}} void solve() { int n = input(); i64 l = input(); vector< int > ws(n); cin >> ws; whole(sort, ws); auto dp = make_vector(ws[0], infll); dp[0] = 0; priority_queue< pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>> > pq; pq.emplace(dp[0], 0); while (not pq.empty()) { auto [c, v] = pq.top(); pq.pop(); if (dp[v] != c) continue; for (const auto &w: ws) { int u = (v + w) % ws[0]; if (chmin(dp[u], c + w)) { pq.emplace(dp[u], u); } } } i64 ans = -1; for (auto &d : dp) { if (d > l) continue; ans += (l - d) / ws[0] + 1; } cout << ans << endl; } signed main() { solve(); }