結果
問題 |
No.288 貯金箱の仕事
|
ユーザー |
![]() |
提出日時 | 2022-09-19 16:57:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 778 ms / 2,000 ms |
コード長 | 742 bytes |
コンパイル時間 | 435 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 70,144 KB |
最終ジャッジ日時 | 2024-12-22 02:32:24 |
合計ジャッジ時間 | 14,947 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
def main() -> None: N, M = (int(elt) for elt in input().split()) A = [int(elt) for elt in input().split()] K = [int(elt) for elt in input().split()] tot = sum(a * k for (a, k) in zip(A, K)) - M # print(f"DEBUG: tot={tot}") MAX_V = A[N - 1] * A[N - 1] INF = 10**18 dp = [INF] * (MAX_V + 1) dp[0] = 0 for i in range(N): for j in range(MAX_V + 1): if j - A[i] >= 0: dp[j] = min(dp[j], dp[j - A[i]] + 1) # print(f"DEBUG: dp={dp}") ans = INF for j in range(MAX_V + 1): if dp[j] == INF: continue rem = tot - j if rem >= 0 and rem % A[N - 1] == 0: ans = min(ans, dp[j] + (rem // A[N - 1])) if ans == INF: ans = -1 print(ans) return if __name__ == '__main__': main()