結果
問題 |
No.1861 Required Number
|
ユーザー |
![]() |
提出日時 | 2023-04-24 12:27:57 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 660 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 227,456 KB |
最終ジャッジ日時 | 2024-11-08 14:37:06 |
合計ジャッジ時間 | 18,079 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 3 WA * 39 MLE * 4 |
ソースコード
N, K = map(int, input().split()) A = list(map(int, input().split())) dp = [[0] * (K + 1) for i in range(N + 1)] dp2 = [[0] * (K + 1) for i in range(N + 1)] dp[0][0] = 1 dp2[0][0] = 1 for i in range(N): for j in range(K + 1): dp[i + 1][j] |= dp[i][j] dp2[i + 1][j] |= dp2[i][j] if j - A[i] >= 0: dp[i + 1][j] |= dp[i][j - A[i]] if j - A[N - 1 - i] >= 0: dp2[i + 1][j] |= dp2[i][j - A[N - 1 - i]] if not dp[N][K]: print(-1) exit() ans = 0 for i in range(1, N): flag = 0 for k in range(K + 1): flag |= (dp[i][K - k] & dp2[N - i - 1][k]) if flag: ans += 1 print(ans)