結果

問題 No.158 奇妙なお使い
ユーザー gew1fw
提出日時 2025-06-12 13:53:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,486 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 274,712 KB
最終ジャッジ日時 2025-06-12 13:55:26
合計ジャッジ時間 12,804 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def can_pay(a1000, a100, a1, d):
    total = a1000 * 1000 + a100 * 100 + a1
    if total < d:
        return False
    max_x = min(a1000, d // 1000)
    for x in range(max_x, -1, -1):
        rem = d - x * 1000
        if rem < 0:
            continue
        max_y = min(a100, rem // 100)
        if rem - max_y * 100 <= a1:
            return True
        if rem <= a1:
            return True
    return False

def main():
    A1000, A100, A1 = map(int, sys.stdin.readline().split())
    Db = int(sys.stdin.readline())
    B1000, B100, B1 = map(int, sys.stdin.readline().split())
    Dc = int(sys.stdin.readline())
    C1000, C100, C1 = map(int, sys.stdin.readline().split())

    max_a1000 = 10000 // 1000
    max_a100 = 10000 // 100
    max_a1 = 10000

    max_tasks = [[[-1 for _ in range(max_a1 + 1)] for __ in range(max_a100 + 1)] for ___ in range(max_a1000 + 1)]

    queue = deque()
    initial_state = (A1000, A100, A1)
    max_tasks[A1000][A100][A1] = 0
    queue.append((A1000, A100, A1, 0))

    max_count = 0

    while queue:
        a1000, a100, a1, count = queue.popleft()
        current_max = max_tasks[a1000][a100][a1]
        if current_max > count:
            continue
        if count > max_count:
            max_count = count

        if can_pay(a1000, a100, a1, Db):
            for x in range(min(a1000, Db // 1000), -1, -1):
                rem = Db - x * 1000
                if rem < 0:
                    continue
                for y in range(min(a100, rem // 100), -1, -1):
                    rem2 = rem - y * 100
                    if rem2 < 0:
                        continue
                    if rem2 > a1:
                        continue
                    new_a1000 = a1000 - x + B1000
                    new_a100 = a100 - y + B100
                    new_a1 = a1 - rem2 + B1
                    if new_a1000 < 0 or new_a100 < 0 or new_a1 < 0:
                        continue
                    if new_a1000 > max_a1000 or new_a100 > max_a100 or new_a1 > max_a1:
                        continue
                    new_count = count + 1
                    if max_tasks[new_a1000][new_a100][new_a1] < new_count:
                        max_tasks[new_a1000][new_a100][new_a1] = new_count
                        queue.append((new_a1000, new_a100, new_a1, new_count))

        if can_pay(a1000, a100, a1, Dc):
            for x in range(min(a1000, Dc // 1000), -1, -1):
                rem = Dc - x * 1000
                if rem < 0:
                    continue
                for y in range(min(a100, rem // 100), -1, -1):
                    rem2 = rem - y * 100
                    if rem2 < 0:
                        continue
                    if rem2 > a1:
                        continue
                    new_a1000 = a1000 - x + C1000
                    new_a100 = a100 - y + C100
                    new_a1 = a1 - rem2 + C1
                    if new_a1000 < 0 or new_a100 < 0 or new_a1 < 0:
                        continue
                    if new_a1000 > max_a1000 or new_a100 > max_a100 or new_a1 > max_a1:
                        continue
                    new_count = count + 1
                    if max_tasks[new_a1000][new_a100][new_a1] < new_count:
                        max_tasks[new_a1000][new_a100][new_a1] = new_count
                        queue.append((new_a1000, new_a100, new_a1, new_count))
    print(max_count)

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