結果

問題 No.1330 Multiply or Divide
ユーザー LyricalMaestro
提出日時 2025-01-20 20:37:17
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,381 bytes
コンパイル時間 2,499 ms
コンパイル使用メモリ 81,476 KB
実行使用メモリ 637,324 KB
最終ジャッジ日時 2025-01-20 20:38:22
合計ジャッジ時間 61,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28 TLE * 17 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/944

import heapq

def main():
    N, M, P = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort(reverse=True)
    p_array = []
    for i in range(N):
        a = A[i]
        p_cnt = 0
        while a % P == 0:
            a //= P
            p_cnt += 1
        p_array.append((a, p_cnt))

    p_set = {}
    for a, p_cnt in p_array:
        if a not in p_set:
            p_set[a] = float("inf")
        p_set[a] = min(p_set[a], p_cnt)
    
    p_array = [(a, p_cnt) for a, p_cnt in p_set.items()]

    queue = []
    seen = {1:0}
    fix = {}
    heapq.heappush(queue, (0, 1))
    answer = float("inf")
    while len(queue) > 0:
        cost, a = heapq.heappop(queue)
        if a in fix:
            continue

        fix[a] = cost
        if a * A[0] > M:
            answer = min(answer, cost + 1)

        for x, p_cnt in p_array:
            new_x = a * x
            if new_x > M:
                continue

            if new_x in fix:
                continue
            
            new_cost = cost + p_cnt + 1
            if new_x not in seen or seen[new_x] > new_cost:
                seen[new_x] = new_cost
                heapq.heappush(queue, (new_cost, new_x))
    
    if answer == float("inf"):
        print(-1)
    else:
        print(answer)


    


    



if __name__ == "__main__":
    main()
0