結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-08 21:57:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 206 ms / 2,000 ms |
コード長 | 879 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 106,460 KB |
最終ジャッジ日時 | 2025-06-20 01:21:15 |
合計ジャッジ時間 | 6,239 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 51 |
ソースコード
mod = 1000000007 eps = 10**-9 inf = 10**17 def main(): import sys input = sys.stdin.readline N, M, P = map(int, input().split()) A = list(map(int, input().split())) if max(A) > M: print(1) exit() B = [1] * 40 for a in A: cnt = 0 aa = a while aa % P == 0: cnt += 1 aa //= P B[cnt] = max(B[cnt], aa) dp = [[-inf] * 1000 for _ in range(40)] dp[0][0] = 1 ans = inf ma = max(A) for i in range(40): for j in range(1000): if i != 0: dp[i][j] = dp[i-1][j] if j - i - 1 >= 0: dp[i][j] = max(dp[i][j], dp[i][j-i-1] * B[i]) if dp[i][j] * ma > M: ans = min(ans, j+1) if ans != inf: print(ans) else: print(-1) if __name__ == '__main__': main()