結果
問題 | No.733 分身並列コーディング |
ユーザー |
![]() |
提出日時 | 2025-03-21 00:23:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,145 ms / 1,500 ms |
コード長 | 723 bytes |
コンパイル時間 | 287 ms |
コンパイル使用メモリ | 81,992 KB |
実行使用メモリ | 112,372 KB |
最終ジャッジ日時 | 2025-03-21 00:23:54 |
合計ジャッジ時間 | 25,104 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
INF = 1 << 60 T = int(input()) N = int(input()) ts = [int(input()) for _ in range(N)] bset = set() for i in range(1 << N): t = sum(ts[j] for j in range(N) if i & (1 << j)) if t <= T: bset.add(i) bit_all = (1 << N) - 1 dp = [[INF] * (1 << N) for _ in range(N+1)] dp[0][0] = 0 for k in range(N): for bit in range(1 << N): if dp[k][bit] <= T: dp[k+1][bit] = 0 for i in range(N): if bit & (1 << i): continue nb = bit | (1 << i) dp[k][nb] = min(dp[k][nb], dp[k][bit] + ts[i]) if dp[k][nb] + ts[i] <= T: dp[k+1][nb] = 0 ans = N for k in range(N): if dp[k][bit_all] == 0: ans = min(ans, k) print(ans)