結果
問題 |
No.1163 I want to be a high achiever
|
ユーザー |
|
提出日時 | 2023-03-02 20:47:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 829 ms / 2,000 ms |
コード長 | 562 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 82,200 KB |
実行使用メモリ | 143,368 KB |
最終ジャッジ日時 | 2024-09-17 14:13:40 |
合計ジャッジ時間 | 11,266 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
INF = 1 << 60 n, x = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for i in range(n): a[i] -= x if all([x < 0 for x in a]): print("-1") exit() cost = - sum(a) if cost <= 0: print("0") exit() dp = {} dp[0] = 0 ans = INF for i in range(n): if a[i] >= 0: continue ndp = {} for k, v in dp.items(): ndp[k] = min(ndp.get(k, INF), v) nxt = k - a[i] if nxt >= cost: ans = min(ans, v + b[i]) else: ndp[nxt] = min(ndp.get(nxt, INF), v + b[i]) dp = ndp print(ans)