結果

問題 No.288 貯金箱の仕事
ユーザー lam6er
提出日時 2025-03-31 17:25:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,130 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 98,260 KB
最終ジャッジ日時 2025-03-31 17:27:24
合計ジャッジ時間 18,673 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 8 TLE * 2 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import deque

def main():
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    K = list(map(int, sys.stdin.readline().split()))
    
    # Calculate GCD of all A's
    d = A[0]
    for a in A[1:]:
        d = math.gcd(d, a)
    if M % d != 0:
        print(-1)
        return
    m = M // d
    a_list = [a // d for a in A]
    
    S = sum(a * k for a, k in zip(a_list, K))
    if m > S:
        print(-1)
        return
    
    # BFS to find minimal coins for representing x (0 <= x <= some_max)
    max_x_for_bfs = 10**6  # Arbitrary limit; might need adjustment
    INF = float('inf')
    min_coins = [INF] * (max_x_for_bfs + 1)
    min_coins[0] = 0
    dq = deque([0])
    
    while dq:
        v = dq.popleft()
        for a in a_list:
            nv = v + a
            if nv > max_x_for_bfs:
                continue
            if min_coins[nv] > min_coins[v] + 1:
                min_coins[nv] = min_coins[v] + 1
                dq.append(nv)
    
    def get_min_coins(x):
        if x > max_x_for_bfs:
            return INF  # Not handled
        return min_coins[x]
    
    best = INF
    
    # Now, iterate through possible k (x = k)
    # Since m + k <= S => k <= S - m
    max_k = S - m
    
    # But how to iterate k? Only those that can be formed and handled by get_min_coins
    # For possible_k, try up to max_k and max_x_for_bfs
    max_possible_k = min(max_k, max_x_for_bfs)
    
    for k in range(0, max_possible_k + 1):
        if min_coins[k] == INF:
            continue
        s = m + k
        total_used = 0
        s_remaining = s
        valid = True
        for i in reversed(range(N)):
            a = a_list[i]
            cnt = min(K[i], s_remaining // a)
            s_remaining -= a * cnt
            total_used += cnt
        if s_remaining == 0:
            total_coins = (sum(K) - total_used) + get_min_coins(k)
            if total_coins < best:
                best = total_coins
    if best != INF:
        print(best)
    else:
        print(-1)

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