結果

問題 No.158 奇妙なお使い
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:25:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,090 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 82,076 KB
実行使用メモリ 79,524 KB
最終ジャッジ日時 2025-04-15 23:26:29
合計ジャッジ時間 7,351 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 4 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    a1000, a100, a1 = map(int, input().split())
    Db = int(input())
    B1000, B100, B1 = map(int, input().split())
    Dc = int(input())
    C1000, C100, C1 = map(int, input().split())

    transactions = [
        (Db, (B1000, B100, B1)),
        (Dc, (C1000, C100, C1))
    ]

    heap = []
    initial_state = (a1000, a100, a1)
    heapq.heappush(heap, (0, initial_state[0], initial_state[1], initial_state[2]))
    steps_dict = {initial_state: 0}
    max_steps = 0

    while heap:
        current_steps_neg, current_1000, current_100, current_1 = heapq.heappop(heap)
        current_steps = -current_steps_neg

        if steps_dict.get((current_1000, current_100, current_1), -1) > current_steps:
            continue

        if current_steps > max_steps:
            max_steps = current_steps

        for D, (r1000, r100, r1) in transactions:
            max_x = min(current_1000, D // 1000)
            for x in range(max_x + 1):
                remaining = D - x * 1000
                if remaining < 0:
                    continue
                max_y = min(current_100, remaining // 100)
                for y in range(max_y + 1):
                    z = remaining - y * 100
                    if z < 0 or z > current_1:
                        continue
                    new_1000_tmp = current_1000 - x
                    new_100_tmp = current_100 - y
                    new_1_tmp = current_1 - z
                    new_1000 = new_1000_tmp + r1000
                    new_100 = new_100_tmp + r100
                    new_1 = new_1_tmp + r1
                    if new_1000 < 0 or new_100 < 0 or new_1 < 0:
                        continue
                    new_state = (new_1000, new_100, new_1)
                    new_steps = current_steps + 1
                    if new_state not in steps_dict or new_steps > steps_dict[new_state]:
                        steps_dict[new_state] = new_steps
                        heapq.heappush(heap, (-new_steps, new_1000, new_100, new_1))

    print(max_steps)

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