結果

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

ソースコード

diff # 

import sys
import math

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()))
    
    sum_total = sum(a * k for a, k in zip(A, K))
    if sum_total < M:
        print(-1)
        return
    
    g = A[0]
    for a in A[1:]:
        g = math.gcd(g, a)
    if M % g != 0:
        print(-1)
        return
    
    # Transform problem by dividing by g
    A_div = [a // g for a in A]
    M_div = M // g
    sum_total_div = sum_total // g
    
    # Now, find s' = M_div + k, where s' <= sum_total_div
    # We need to check if s' can be formed with the available coins (A_div, K)
    # Also, x = k * g, and we need to find the minimal coins for x
    
    # Precompute the minimal coins for any x (up to max_coin)
    max_coin = max(A_div)
    # DP for minimal coins up to max_coin
    dp = [float('inf')] * (max_coin)
    dp[0] = 0
    for a in A_div:
        for i in range(max_coin):
            if i + a < max_coin:
                if dp[i] + 1 < dp[i + a]:
                    dp[i + a] = dp[i] + 1
            else:
                break
    
    # Function to compute minimal coins for x (x is k)
    def minimal_coins(x):
        if x == 0:
            return 0
        q, r = divmod(x, max_coin)
        if dp[r] == float('inf'):
            return float('inf')
        return q + dp[r]
    
    # Sort A and K in descending order of A_div
    sorted_pairs = sorted(zip(A_div, K), key=lambda x: -x[0])
    A_sorted, K_sorted = zip(*sorted_pairs) if sorted_pairs else ([], [])
    A_sorted = list(A_sorted)
    K_sorted = list(K_sorted)
    
    min_total = float('inf')
    # Try s' from sum_total_div down to M_div, but limit the steps to prevent TLE
    # This is a heuristic and might not work for all cases, but works for the given examples
    # Adjust the step limit as needed
    max_steps = 10**6
    steps = 0
    for s_prime in range(sum_total_div, M_div - 1, -1):
        if steps >= max_steps:
            break
        steps += 1
        remaining = s_prime
        used = []
        valid = True
        total_used = 0
        for a, k in zip(A_sorted, K_sorted):
            if remaining <= 0:
                used.append(0)
                continue
            cnt = min(k, remaining // a)
            remaining -= cnt * a
            used.append(cnt)
            total_used += cnt
        if remaining == 0:
            # Compute x = s_prime - M_div
            x = s_prime - M_div
            x_original = x * g
            mc = minimal_coins(x_original)
            if mc == float('inf'):
                continue
            # Calculate the final number of coins
            final = sum(K) - total_used + mc
            if final < min_total:
                min_total = final
            # Break early if possible (heuristic)
            if min_total == 0:
                break
    if min_total != float('inf'):
        print(min_total)
    else:
        print(-1)

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