結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2021-11-08 10:25:01 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 880 bytes |
コンパイル時間 | 1,712 ms |
コンパイル使用メモリ | 142,512 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-15 21:03:08 |
合計ジャッジ時間 | 2,681 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;int main() {int N, M;cin >> N >> M;int score[N][N];memset(score, 0, sizeof(score));int a, b, c;for (int i = 0; i < M; ++i) {cin >> a >> b >> c;score[a][b] = c;}int dp[1 << N];memset(dp, 0, sizeof(dp));for (int mask = 0; mask < (1 << N); ++mask) {for (int i = 0; i < N; ++i) {if (mask >> i & 1) continue;int v = 0;for (int j = 0; j < N; ++j) {if (mask >> j & 1) {v += score[j][i];}}int nmask = mask | (1 << i);dp[nmask] = max(dp[nmask], dp[mask] + v);}}cout << dp[(1 << N) - 1] << endl;return 0;}