結果

問題 No.288 貯金箱の仕事
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:22:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,194 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 178,876 KB
最終ジャッジ日時 2025-06-12 16:22:52
合計ジャッジ時間 4,209 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def readints():
    return list(map(int, sys.stdin.readline().split()))

def main():
    N, M = readints()
    A = readints()
    K = readints()
    
    # Compute S_max
    S_max = sum(a * k for a, k in zip(A, K))
    if S_max < M:
        print(-1)
        return
    
    x = S_max - M
    
    # Check if x can be formed using the coins
    # Using BFS to find the minimal number of coins
    mod = A[0]
    max_mod = max(A)
    visited = {}
    queue = deque()
    queue.append((0, 0))
    visited[0] = 0
    found = False
    min_coins = None
    while queue:
        current, coins = queue.popleft()
        if current == x:
            min_coins = coins
            found = True
            break
        for a in A:
            next_val = current + a
            next_coins = coins + 1
            if next_val > x + max(A):
                continue
            if next_val not in visited or next_coins < visited[next_val]:
                visited[next_val] = next_coins
                queue.append((next_val, next_coins))
    
    if not found:
        print(-1)
        return
    
    print(min_coins)

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