結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2024-10-16 15:45:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 85 ms / 5,000 ms |
コード長 | 940 bytes |
コンパイル時間 | 531 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 70,528 KB |
最終ジャッジ日時 | 2024-10-16 15:45:10 |
合計ジャッジ時間 | 2,729 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
# dp[s] = 今までに並べた品物の集合# 追加でitem2を置くときに、既存の集合にitem1があれば得点が得られるN,M = map(int,input().split())from collections import defaultdictdic = defaultdict(list) # item2をキーに、[item1, score]を持つfor _ in range(M):item1, item2, score = map(int,input().split())dic[item2].append([item1, score])dp = [0] * (1 << N)for status in range(1 << N):for item2 in range(N): # 次に置くアイテムif (status >> item2) & 1: # 置き済みcontinuenew_status = status | (1 << item2)point = 0 # item2を置いたときに得られる得点for item1, score in dic[item2]: # item1が置かれていれば得点が得られるif (status >> item1) & 1: # item1が置かれているpoint += scoredp[new_status] = max(dp[new_status], dp[status] + point)print(dp[-1])