結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-09 00:07:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 870 bytes |
コンパイル時間 | 2,024 ms |
コンパイル使用メモリ | 169,484 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 19:21:19 |
合計ジャッジ時間 | 5,708 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 38 WA * 8 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (long long i = 0; i < (n); ++i) using ll = long long; using P = pair<ll,ll>; using PP = pair<P,ll>; using vec = vector<ll>; using vecp = vector<P>; using mat = vector<vec>; using matp = vector<vecp>; const ll MOD = 1e9+7; const ll INF = 1e18; #define all(v) v.begin(), v.end() int main(){ ll N,M,P; cin >> N >> M >> P; vec A(N),B(30,0); rep(i,N){ cin >> A.at(i); ll t=0; while(A.at(i)%P==0){ t++; A.at(i)/=P; } B.at(t)=max(B.at(t),A.at(i)); } rep(i,30){ if(B.at(i)>1){ break; } if(i==29){ cout << -1 << endl; return 0; } } vec dp(900,0); dp.at(0)=1; rep(i,900){ if(dp.at(i)>M){ cout << i << endl; return 0; } rep(j,30){ dp.at(i+j+1)=max(dp.at(i+j+1),dp.at(i)*B.at(j)); } } }