結果
問題 | No.1163 I want to be a high achiever |
ユーザー |
![]() |
提出日時 | 2021-07-08 20:52:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 927 ms / 2,000 ms |
コード長 | 626 bytes |
コンパイル時間 | 219 ms |
コンパイル使用メモリ | 82,348 KB |
実行使用メモリ | 144,660 KB |
最終ジャッジ日時 | 2024-07-01 12:34:00 |
合計ジャッジ時間 | 12,558 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
n, x = map(int, input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) INF = 10**18 A = [a-x for a in A] s = sum(A) if s >= 0: print(0) exit() if max(A) < 0: print(-1) exit() from collections import defaultdict dp = defaultdict(lambda: INF) dp[s] = 0 for a, b in zip(A, B): if a >= 0: continue nx = defaultdict(lambda: INF) for k, v in dp.items(): nx[k] = min(nx[k], v) nx[k-a] = min(nx[k-a], v+b) dp = nx ans = INF for k, v in dp.items(): if k >= 0: ans = min(ans, v) if ans != INF: print(ans) else: print(-1)