結果
問題 | No.1782 ManyCoins |
ユーザー |
![]() |
提出日時 | 2021-12-11 00:11:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,849 ms / 2,000 ms |
コード長 | 868 bytes |
コンパイル時間 | 1,673 ms |
コンパイル使用メモリ | 178,320 KB |
実行使用メモリ | 21,072 KB |
最終ジャッジ日時 | 2024-07-18 20:06:59 |
合計ジャッジ時間 | 8,709 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long INF = 1000000000000000000; int main(){ int N; long long L; cin >> N >> L; vector<int> W(N); for (int i = 0; i < N; i++){ cin >> W[i]; } sort(W.begin(), W.end()); vector<long long> dp(W[0], INF); priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; pq.push(make_pair(0, 0)); while (!pq.empty()){ long long x = pq.top().first; int v = pq.top().second; pq.pop(); if (dp[v] == INF){ dp[v] = x; for (int j = 1; j < N; j++){ int w = (v + W[j]) % W[0]; if (dp[w] == INF){ pq.push(make_pair(x + W[j], w)); } } } } long long ans = 0; for (int i = 0; i < W[0]; i++){ if (dp[i] <= L){ ans += (L - dp[i]) / W[0] + 1; } } cout << ans - 1 << endl; }