結果
問題 | No.1782 ManyCoins |
ユーザー |
![]() |
提出日時 | 2021-12-11 09:51:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 640 bytes |
コンパイル時間 | 2,135 ms |
コンパイル使用メモリ | 201,048 KB |
最終ジャッジ日時 | 2025-01-26 07:46:31 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 48 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;#define rep(i,N) for(int i=0;i<N;++i)int N,w[20],d;ll L,dp[1000000],ans;bool vis[1000000];int main(){cin.tie(0)->sync_with_stdio(0);cin>>N>>L;rep(i,N){cin>>w[i];d=gcd(d,w[i]);}L/=d;rep(i,N)w[i]/=d;sort(w,w+N);priority_queue<ll,vector<ll>,greater<ll>> que;que.emplace(0);while(!que.empty()){ll x=que.top();que.pop();int a=x%w[0];if(vis[a])continue;vis[a]=true;rep(i,N)if(!vis[(a+w[i])%w[0]])que.emplace(x+w[i]);}rep(i,w[0]){if(L<dp[i])continue;ans+=(L-dp[i])/w[0]+1;}cout<<ans<<'\n';}