結果
問題 | No.1330 Multiply or Divide |
ユーザー |
|
提出日時 | 2021-01-08 23:39:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 677 bytes |
コンパイル時間 | 1,753 ms |
コンパイル使用メモリ | 194,820 KB |
最終ジャッジ日時 | 2025-01-17 14:45:16 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 WA * 1 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:9:26: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 9 | lint n,m,p; scanf("%lld%lld%lld",&n,&m,&p); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:11:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 11 | rep(i,n) scanf("%lld",&a[i]); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(n);i++)using namespace std;using lint=long long;int main(){lint n,m,p; scanf("%lld%lld%lld",&n,&m,&p);vector<lint> a(n);rep(i,n) scanf("%lld",&a[i]);if(m==1){puts("0");return 0;}vector<lint> b(n),e(n); // a[i] = b[i] * p^e[i]rep(i,n){for(b[i]=a[i];b[i]%p==0;b[i]/=p) e[i]++;}vector<lint> dp(1000,-1);dp[0]=1;rep(i,n){rep(w,1000-(e[i]+1)) if(dp[w]!=-1) {dp[w+e[i]+1]=min(max(dp[w+e[i]+1],dp[w]*b[i]),m);}}lint mx=*max_element(a.begin(),a.end());lint tar=m/mx+1;rep(w,1000){if(dp[w]>=tar){printf("%d\n",w+1);return 0;}}puts("-1");return 0;}