結果
問題 |
No.1861 Required Number
|
ユーザー |
![]() |
提出日時 | 2023-04-24 12:32:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 461 ms / 2,500 ms |
コード長 | 666 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 82,092 KB |
実行使用メモリ | 227,056 KB |
最終ジャッジ日時 | 2024-11-20 14:52:21 |
合計ジャッジ時間 | 14,389 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 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 = N for i in range(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)