結果

問題 No.733 分身並列コーディング
コンテスト
ユーザー tobusakana
提出日時 2022-10-23 22:59:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 136 ms / 1,500 ms
コード長 956 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 94,764 KB
最終ジャッジ日時 2024-07-02 11:41:39
合計ジャッジ時間 5,581 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
readline = sys.stdin.readline

T = int(readline())
N = int(readline())
P = [int(readline()) for i in range(N)]
# dp[num][S] = 分身の数num, 解いた問題の集合Sのときに、最後の分身が残している時間

dp = [[-1] * (1 << N) for i in range(N + 1)]
dp[0][0] = 0
for status in range(1 << N):
  for num in range(N + 1):
    if dp[num][status] == -1:
      continue
    for target in range(N): # 次に解く問題
      if (status >> target) & 1:
        continue
      next_status = status | (1 << target)
      if dp[num][status] >= P[target]: # 今の分身で解ける。
        if dp[num][next_status] < dp[num][status] - P[target]:
          dp[num][next_status] = dp[num][status] - P[target]
      else: # 新たな分身が必要
        if dp[num + 1][next_status] < T - P[target]:
          dp[num + 1][next_status] = T - P[target]
        

for i in range(N + 1):
  if dp[i][-1] != -1:
    print(i)
    break
0