結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-08 23:30:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 1,154 bytes |
コンパイル時間 | 1,195 ms |
コンパイル使用メモリ | 97,720 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-11-16 19:28:47 |
合計ジャッジ時間 | 4,389 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#include <tuple>#define mkp make_pair#define mkt make_tuple#define rep(i,n) for(int i = 0; i < (n); ++i)#define all(v) v.begin(),v.end()using namespace std;typedef long long ll;const ll MOD=1e9+7;template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}const ll INF=1e18;const int LIM=2e3;int main(){cin.tie(0);ios::sync_with_stdio(false);ll N,M,P;cin>>N>>M>>P;vector<ll> A(N);rep(i,N) cin>>A[i];vector<int> B(N);vector<ll> C(N);rep(i,N){int num=0;int val=A[i];while(val%P==0){val/=P;num++;}B[i]=val;C[i]=num;}ll ma=*max_element(all(A));vector<ll> dp(LIM+1,0);dp[0]=1;for(int i=0;i<LIM;i++){if(dp[i]*ma>M){cout<<i+1<<endl;return 0;}if(dp[i]==0) continue;ll value=dp[i];for(int j=0;j<N;j++){if(i+C[j]+1<=LIM) chmax(dp[i+C[j]+1],value*B[j]);}}cout<<-1<<endl;return 0;}