結果

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

ソースコード

diff # 

import heapq

def main():
    A1000, A100, A1 = map(int, input().split())
    D_b = int(input())
    B1000, B100, B1 = map(int, input().split())
    D_c = int(input())
    C1000, C100, C1 = map(int, input().split())
    
    B_trans = (D_b, B1000, B100, B1)
    C_trans = (D_c, C1000, C100, C1)
    
    max_steps = {}
    heap = []
    initial_state = (A1000, A100, A1)
    max_steps[initial_state] = 0
    heapq.heappush(heap, (0, A1000, A100, A1))
    
    max_result = 0
    
    while heap:
        current_neg_steps, a, b, c = heapq.heappop(heap)
        current_steps = -current_neg_steps
        
        if current_steps < max_steps.get((a, b, c), -1):
            continue
        
        if current_steps > max_result:
            max_result = current_steps
        
        # Process B transaction
        D, rec_a, rec_b, rec_c = B_trans
        max_x = min(a, D // 1000)
        for x in range(max_x + 1):
            remaining = D - x * 1000
            if remaining < 0:
                break
            max_y = min(b, remaining // 100)
            for y in range(max_y + 1):
                remaining_after_y = remaining - y * 100
                if remaining_after_y < 0:
                    break
                z = remaining_after_y
                if z > c:
                    continue
                new_a = a - x + rec_a
                new_b = b - y + rec_b
                new_c = c - z + rec_c
                new_steps = current_steps + 1
                if new_steps > max_steps.get((new_a, new_b, new_c), -1):
                    max_steps[(new_a, new_b, new_c)] = new_steps
                    heapq.heappush(heap, (-new_steps, new_a, new_b, new_c))
        
        # Process C transaction
        D, rec_a, rec_b, rec_c = C_trans
        max_x = min(a, D // 1000)
        for x in range(max_x + 1):
            remaining = D - x * 1000
            if remaining < 0:
                break
            max_y = min(b, remaining // 100)
            for y in range(max_y + 1):
                remaining_after_y = remaining - y * 100
                if remaining_after_y < 0:
                    break
                z = remaining_after_y
                if z > c:
                    continue
                new_a = a - x + rec_a
                new_b = b - y + rec_b
                new_c = c - z + rec_c
                new_steps = current_steps + 1
                if new_steps > max_steps.get((new_a, new_b, new_c), -1):
                    max_steps[(new_a, new_b, new_c)] = new_steps
                    heapq.heappush(heap, (-new_steps, new_a, new_b, new_c))
    
    print(max_result)

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