結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2021-02-03 23:17:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 2,501 bytes |
コンパイル時間 | 1,050 ms |
コンパイル使用メモリ | 116,036 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 06:26:35 |
合計ジャッジ時間 | 1,933 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#pragma region#define _USE_MATH_DEFINES#include <iostream>#include <string>#include <algorithm>#include <cmath>#include <cstdlib>#include <vector>#include <map>#include <queue>#include <stack>#include <set>#include <list>#include <iomanip>#include <cstdint>#include <bitset>#include <sstream>#include <regex>#include <fstream>#include <array>//#include <atcoder/all>using namespace std;//using namespace atcoder;////using mint = modint1000000007;//using mint = modint998244353;////using mint = modint;typedef long long ll;using vi = vector<int>;using vvi = vector<vi>;using vl = vector<ll>;using vvl = vector<vl>;using pint = pair<int, int>;using pll = pair<ll, ll>;//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#pragma region UnionFindstruct UnionFind{vector<int> par;UnionFind(int n) : par(n, -1) {}void init(int n) { par.assign(n, -1); }int root(int x){if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(int x, int y){return root(x) == root(y);}bool merge(int x, int y){x = root(x); y = root(y);if (x == y) return false;if (par[x] > par[y]) swap(x, y);par[x] += par[y];par[y] = x;return true;}int size(int x){return -par[root(x)];}};#pragma endregion#pragma region GCDll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a%b);}#pragma endregion#pragma region LCMll lcm(ll a, ll b){return a / gcd(a, b) * b;}#pragma endregion#pragma region chmintemplate<class T> inline bool chmin(T& a, T b){if (a > b){a = b;return true;}return false;}#pragma endregion#pragma region chmaxtemplate<class T> inline bool chmax(T& a, T b){if (a < b){a = b;return true;}return false;}#pragma endregionbool out(int x, int y, int h, int w){if (x < 0 || h <= x || y < 0 || w <= y)return true;else return false;}#pragma endregionint main(){int n, m; cin >> n >> m;vvi v(n, vi(n));rep(i, m){int it1, it2, s; cin >> it1 >> it2 >> s;v[it1][it2] = s;}vi dp(1 << n);rep(S, 1 << n){vi used(n);rep(i, n)if (S >> i & 1)used[i] = 1;rep(i, n){if (S >> i & 1)continue;int tmp = 0;rep(j, n)if (!used[j])tmp += v[i][j];chmax(dp[S + (1 << i)], dp[S] + tmp);}}cout << dp[(1 << n) - 1] << endl;}