結果
問題 |
No.1861 Required Number
|
ユーザー |
|
提出日時 | 2024-05-10 23:00:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 614 ms / 2,500 ms |
コード長 | 885 bytes |
コンパイル時間 | 163 ms |
コンパイル使用メモリ | 82,496 KB |
実行使用メモリ | 234,704 KB |
最終ジャッジ日時 | 2024-12-20 07:09:25 |
合計ジャッジ時間 | 17,793 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 MLE * 4 |
ソースコード
n, k = map(int, input().split()) A = list(map(int, input().split())) DPl = [[0 for _ in range(k + 1)] for _ in range(n + 1)] DPr = [[0 for _ in range(k + 1)] for _ in range(n + 1)] DPl[0][0] = 1 DPr[n][0] = 1 for i in range(n): a = A[i] for j in range(k + 1): if DPl[i][j] > 0: DPl[i + 1][j] |= DPl[i][j] if j + a <= k: DPl[i + 1][j + a] |= DPl[i][j] for i in range(n - 1, -1, -1): a = A[i] for j in range(k + 1): if DPr[i + 1][j] > 0: DPr[i][j] |= DPr[i + 1][j] if j + a <= k: DPr[i][j + a] |= DPr[i + 1][j] ans = 0 if DPl[n][k]: for i in range(n): flag = True for j in range(k + 1): if DPl[i][j] and DPr[i + 1][k - j]: flag = False break if flag: ans += 1 else: ans = -1 print(ans)