結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2016-08-14 02:35:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 76 ms / 5,000 ms |
コード長 | 824 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 82,776 KB |
実行使用メモリ | 70,148 KB |
最終ジャッジ日時 | 2024-11-07 16:37:59 |
合計ジャッジ時間 | 2,155 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
n, m = map(int,input().split())item = [[0] * n for i in range(n)]for i in range(m):item1, item2, score = map(int,input().split())item1 -= 1item2 -= 1item[item1][item2] = scoredp = [0] * (1 << n)#既に並べた品物の集合を表すfor i in range(1 << n):for j in range(n):#品物jが並べられているif (i >> j) % 2 == 1:continue#品物jが並べられていないok = Trueget_score = 0for k in range(n):#品物kが並べられているif (i >> k) % 2 == 0:#品物j が品物k より先に並べられたという情報があったときget_score += item[j][k]dp[i | (1 << j)] = max(dp[i | (1 << j)], dp[i] + get_score)print(dp[(1 << n) - 1])