結果

問題 No.733 分身並列コーディング
コンテスト
ユーザー tobusakana
提出日時 2022-10-23 22:59:45
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 96 ms / 1,500 ms
コード長 956 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 137 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 96,896 KB
最終ジャッジ日時 2026-03-23 20:02:36
合計ジャッジ時間 4,557 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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