結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2018-04-17 16:45:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 1,215 bytes |
コンパイル時間 | 1,538 ms |
コンパイル使用メモリ | 166,872 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 04:10:46 |
合計ジャッジ時間 | 2,317 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))using ll = long long;using P = pair<int, int>;using namespace std;template<class T> void vin(vector<T>& v, int n) {v.resize(n);for (int i = 0; i < n; ++i) {cin >> v[i];}}int N, M;// dp[S][v] := Sの立っているビットが前に置かれている状態のときの価値の最大値int dp[1<<15];int item[200][200];int solve(int S) {int& res = dp[S];if (res >= 0) return res;if (S == (1 << N) - 1) {return (res = 0);}for (int u = 0; u < N; ++u) {if (!(S >> u & 1)) {int score = 0;for (int k = 0; k < N; ++k) {if (S >> k & 1) {if (item[k][u] == -1) continue;score += item[k][u];}}res = max(res, solve(S | 1 << u) + score);}}return res;}int main() {cin >> N >> M;fill(item[0], item[200], -1);rep(i, M) {int t1, t2, sc;cin >> t1 >> t2 >> sc;item[t1][t2] = sc;}fill(dp, dp+(1<<15), -1);cout << solve(0) << endl;return 0;}