結果

問題 No.288 貯金箱の仕事
ユーザー rpy3cpprpy3cpp
提出日時 2015-10-10 13:36:05
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,610 bytes
コンパイル時間 93 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-07-20 04:59:31
合計ジャッジ時間 3,312 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 32 ms
11,392 KB
testcase_04 AC 32 ms
11,392 KB
testcase_05 AC 32 ms
11,392 KB
testcase_06 AC 32 ms
11,392 KB
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
権限があれば一括ダウンロードができます

ソースコード

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)
    dp[0] = 0
    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