結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2023-08-23 08:00:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,460 bytes |
コンパイル時間 | 3,880 ms |
コンパイル使用メモリ | 261,524 KB |
最終ジャッジ日時 | 2025-02-16 12:28:26 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 TLE * 1 -- * 44 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using ld=long double; ld pie=3.141592653589793; ll mod=998244353; ll inf=1009999999999999990; int main(){ ll n,m,p; cin >> n >> m >> p; vector<ll>a(n); for (ll i = 0; i < n; i++) { cin >> a[i]; } map<ll,ll>memo; memo[1]=1; priority_queue<ll>pq; map<ll,ll>mm; pq.push(1); ll ans=inf; while (!pq.empty()) { ll v=pq.top(); pq.pop(); mm[v]=0; if (v>=m) { ans=min(ans,memo[v]); } if (ans<=memo[v]) { continue; } if (v%p==0) { v/=p; ll x=memo[v]; if (x==0||memo[v]>memo[v*p]+1) { memo[v]=memo[v*p]+1; if (mm[v]==0) { pq.push(v); mm[v]++; } } continue; } for (ll i = 0; i < n; i++) { ll x=memo[v*a[i]]; if (x==0||x>memo[v]+1) { memo[v*a[i]]=memo[v]+1; if (mm[v*a[i]]==0) { pq.push(v*a[i]); mm[v*a[i]]++; } } } } if (ans==inf) { cout << -1 << endl; }else{ cout << ans-1 << endl; } }