結果
問題 | No.733 分身並列コーディング |
ユーザー |
![]() |
提出日時 | 2021-03-17 17:43:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 660 ms / 1,500 ms |
コード長 | 437 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 81,752 KB |
実行使用メモリ | 66,560 KB |
最終ジャッジ日時 | 2024-11-15 10:14:29 |
合計ジャッジ時間 | 9,319 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
T,n,*a = map(int,open(0).read().split()) N = 1<<n lst = [0]*N for i in range(n): for j in range(1<<i): lst[j+(1<<i)] = lst[j] + a[i] for i in range(N): lst[i] = int(lst[i] <= T) dp = [n+9]*N dp[0] = 0 for mask in range(1,N): if lst[mask]: dp[mask] = 1 continue j = mask mmask = mask&(mask-1) while j: dp[mask] = min(dp[mask],dp[j]+dp[mask^j]) j = (j-1)&mmask print(dp[-1])