結果
問題 |
No.733 分身並列コーディング
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:40:18 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,801 bytes |
コンパイル時間 | 148 ms |
コンパイル使用メモリ | 82,756 KB |
実行使用メモリ | 188,788 KB |
最終ジャッジ日時 | 2025-03-20 20:40:28 |
合計ジャッジ時間 | 3,293 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | TLE * 1 -- * 45 |
ソースコード
import sys from collections import deque def solve(): T_val = int(sys.stdin.readline()) N = int(sys.stdin.readline()) times = [int(sys.stdin.readline()) for _ in range(N)] times.sort(reverse=True) # Sorting for efficient pruning full_mask = (1 << N) - 1 for k in range(1, N + 1): dp = {} initial = tuple([0] * k) dp[0] = initial queue = deque([0]) found = False while queue: mask = queue.popleft() current = list(dp[mask]) # Find the first unset bit (next problem to assign) for i in range(N): if not (mask & (1 << i)): ti = times[i] # Try to add this problem to each possible group for g in range(k): if current[g] + ti > T_val: continue new_current = current.copy() new_current[g] += ti new_current_sorted = sorted(new_current) new_mask = mask | (1 << i) if new_mask == full_mask: found = True break new_state = tuple(new_current_sorted) if new_mask not in dp or new_state < dp[new_mask]: dp[new_mask] = new_state queue.append(new_mask) if found: break if found: break if found: break if found: print(k) return print(N) # Fallback, though constraints ensure it's not necessary if __name__ == "__main__": solve()