結果

問題 No.1330 Multiply or Divide
ユーザー maspymaspy
提出日時 2021-01-08 22:35:55
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 428 ms / 2,000 ms
コード長 992 bytes
コンパイル時間 585 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 29,500 KB
最終ジャッジ日時 2024-11-16 19:23:55
合計ジャッジ時間 5,708 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main(N, M, p, A):
# A = B * P^K
B = [0] * N
K = [0] * N
for i, x in enumerate(A):
e = 0
while x % p == 0:
e += 1
x //= p
B[i], K[i] = x, e
# K max_A
AA = [0] * 30
BB = [0] * 30
for a, b, k in zip(A, B, K):
if AA[k] < a:
AA[k] = a
BB[k] = b
A, B = AA, BB
# x
MAX = 500
D = [1] * (MAX * 2)
for i in range(MAX):
x = D[i]
for k in range(30):
a, b = A[k], B[k]
if a == 0:
continue
if x * a > M:
return i + 1
to = x * b
D[i + k + 1] = max(D[i + k + 1], to)
return -1
N, M, P = map(int, readline().split())
A = list(map(int, readline().split()))
print(main(N, M, P, A))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0