結果

問題 No.288 貯金箱の仕事
コンテスト
ユーザー rpy3cpp
提出日時 2015-10-10 13:32:19
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,596 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 89,088 KB
最終ジャッジ日時 2024-07-20 04:59:26
合計ジャッジ時間 10,477 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other AC * 4 RE * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import fractions


def read_data():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))
    Ks = list(map(int, input().split()))
    return N, M, As, Ks


def solve(N, M, As, Ks):
    total = sum(a * k for a, k in zip(As, Ks))
    if total < M:
        return -1
    T = total - M
    if T == 0:
        return 0
    if T < As[0]:
        return -1
    if N == 1:
        if T % As[0]:
            return -1
        else:
            return T // As[0]
    limits = set_limits(As)
    end = min(T, sum((limit - 1) * a for limit, a in zip(limits, As[:-1])))
    dp = do_dp(As, limits, end)
    ans = float('inf')
    A = As[-1]
    r = T % A
    for idx in range(r, end + 1, A):
        coins= (T - idx) // A + dp[idx]
        if ans > coins:
            ans = coins
    if ans == float('inf'):
        ans = -1
    return ans


def set_limits(As):
    n = len(As)
    limits = [float('inf')] * n
    for i in range(n - 1):
        ai = As[i]
        for j in range(i + 1, n):
            aj = As[j]
            gcd = fractions.gcd(ai, aj)
            limit_i = aj // gcd
            limits[i] = min(limits[i], limit_i)
    return limits


def do_dp(As, limits, end):
    INF = float('inf')
    dp = [INF] * (end + 1)
    last = 0
    for a, limit in zip(As[:-1], limits[:-1]):
        last += a * (limit - 1)
        dp[a] = 1
        for i in range(min(last, end) - a + 1):
            if dp[i] != INF:
                j = i + a
                dp[j] = min(dp[j], dp[i] + 1)
    return dp


N, M, As, Ks = read_data()
ans = solve(N, M, As, Ks)
print(solve(N, M, As, Ks))
0