結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
|
提出日時 | 2021-05-18 04:20:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 238 ms / 5,000 ms |
コード長 | 869 bytes |
コンパイル時間 | 276 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 90,368 KB |
最終ジャッジ日時 | 2024-10-07 18:42:03 |
合計ジャッジ時間 | 4,000 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#region Header#!/usr/bin/env python3# from typing import *import sysimport ioimport mathimport collectionsimport decimalimport itertoolsimport bisectimport heapqdef input():return sys.stdin.readline()[:-1]# sys.setrecursionlimit(1000000)#endregion# _INPUT = """# paste here...# """# sys.stdin = io.StringIO(_INPUT)def main():N, M = map(int, input().split())score = [[0] * N for _ in range(N)]for _ in range(M):i, j, n = map(int, input().split())score[i-1][j-1] = ndp = [0] * (1<<N)for s in range(1<<N):for i in range(N):if s & (1<<i):continuescore1 = sum(score[j][i] for j in range(N) if s & (1<<j))dp[s | (1<<i)] = max(dp[s | (1<<i)], dp[s] + score1)ans = dp[(1<<N)-1]print(ans)if __name__ == '__main__':main()