結果

問題 No.1782 ManyCoins
ユーザー kiyoshi0205
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0