結果

問題 No.158 奇妙なお使い
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:29:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,435 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 81,416 KB
実行使用メモリ 848,128 KB
最終ジャッジ日時 2025-04-15 23:31:11
合計ジャッジ時間 5,670 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 3 WA * 1 MLE * 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())

    initial_sum = A1000 * 1000 + A100 * 100 + A1
    max_step = 0

    from collections import defaultdict

    max_a1000 = defaultdict(int)
    max_a100 = defaultdict(int)
    max_a1 = defaultdict(int)
    steps = defaultdict(int)

    max_a1000[initial_sum] = A1000
    max_a100[initial_sum] = A100
    max_a1[initial_sum] = A1
    steps[initial_sum] = 0

    heap = []
    heapq.heappush(heap, (-0, initial_sum))

    while heap:
        neg_step, S = heapq.heappop(heap)
        current_step = -neg_step

        if current_step < steps[S]:
            continue

        if current_step > max_step:
            max_step = current_step

        a1000 = max_a1000[S]
        a100 = max_a100[S]
        a1 = max_a1[S]

        if S >= Db:
            rem = Db
            use_1000 = min(rem // 1000, a1000)
            rem -= use_1000 * 1000
            use_100 = min(rem // 100, a100)
            rem -= use_100 * 100
            if rem <= a1:
                new_a1000 = a1000 - use_1000 + B1000
                new_a100 = a100 - use_100 + B100
                new_a1_val = a1 - rem + B1
                S_new = new_a1000 * 1000 + new_a100 * 100 + new_a1_val
                if S_new >= 0:
                    update = False
                    if new_a1000 > max_a1000.get(S_new, -1):
                        max_a1000[S_new] = new_a1000
                        update = True
                    if new_a100 > max_a100.get(S_new, -1):
                        max_a100[S_new] = new_a100
                        update = True
                    if new_a1_val > max_a1.get(S_new, -1):
                        max_a1[S_new] = new_a1_val
                        update = True
                    if update:
                        new_step = current_step + 1
                        if new_step > steps.get(S_new, -1):
                            steps[S_new] = new_step
                            heapq.heappush(heap, (-new_step, S_new))

        if S >= Dc:
            rem = Dc
            use_1000 = min(rem // 1000, a1000)
            rem -= use_1000 * 1000
            use_100 = min(rem // 100, a100)
            rem -= use_100 * 100
            if rem <= a1:
                new_a1000 = a1000 - use_1000 + C1000
                new_a100 = a100 - use_100 + C100
                new_a1_val = a1 - rem + C1
                S_new = new_a1000 * 1000 + new_a100 * 100 + new_a1_val
                if S_new >= 0:
                    update = False
                    if new_a1000 > max_a1000.get(S_new, -1):
                        max_a1000[S_new] = new_a1000
                        update = True
                    if new_a100 > max_a100.get(S_new, -1):
                        max_a100[S_new] = new_a100
                        update = True
                    if new_a1_val > max_a1.get(S_new, -1):
                        max_a1[S_new] = new_a1_val
                        update = True
                    if update:
                        new_step = current_step + 1
                        if new_step > steps.get(S_new, -1):
                            steps[S_new] = new_step
                            heapq.heappush(heap, (-new_step, S_new))

    print(max_step)

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