結果
問題 | No.733 分身並列コーディング |
ユーザー |
![]() |
提出日時 | 2025-03-31 17:42:02 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 890 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 82,556 KB |
実行使用メモリ | 76,756 KB |
最終ジャッジ日時 | 2025-03-31 17:43:32 |
合計ジャッジ時間 | 21,681 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 TLE * 3 |
ソースコード
T = int(input()) N = int(input()) t = [int(input()) for _ in range(N)] # Precompute the sum of time for each possible subset of problems sum_mask = [0] * (1 << N) for mask in range(1 << N): total = 0 for i in range(N): if mask & (1 << i): total += t[i] sum_mask[mask] = total INF = float('inf') dp = [INF] * (1 << N) dp[0] = 0 # Base case: no problems solved requires 0 clones for mask in range(1 << N): if dp[mask] == INF: continue complement = ((1 << N) - 1) ^ mask subset = complement while True: if subset != 0: if sum_mask[subset] <= T: new_mask = mask | subset if dp[new_mask] > dp[mask] + 1: dp[new_mask] = dp[mask] + 1 if subset == 0: break subset = (subset - 1) & complement full_mask = (1 << N) - 1 print(dp[full_mask])