結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2019-06-06 16:30:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 1,393 bytes |
コンパイル時間 | 1,097 ms |
コンパイル使用メモリ | 99,568 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-25 10:57:42 |
合計ジャッジ時間 | 1,693 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include <cstdlib>#include <math.h>#include <cmath>#include<cctype>#include<string>#include<set>#include<iomanip>#include <map>#include<algorithm>#include <functional>#include<vector>#include<climits>#include<stack>#include<queue>#include<bitset>#include <deque>#include <climits>#include <typeinfo>#include <utility>using namespace std;using ll = long long;using R = double;using Data = pair < ll, vector <ll>>;const ll MOD = 1e9 + 7;const ll inf = 1LL << 60;struct edge { ll from; ll to; ll cost; };typedef tuple<ll, ll, ll>T;typedef pair<ll, ll>pll;#define all(x) (x).begin(),(x).end()#define rep(i,m,n) for(ll i = m;i < n;++i)#define pb push_back#define fore(i,a) for(auto &i:a)#define rrep(i,m,n) for(ll i = m;i >= n;--i)#define INF INT_MAX/2int N, M;vector<pair<int,int>>e[20];int memo[1 << 14];int dfs(int msk) {if (msk == 0)return 0;if (memo[msk] != -1)return memo[msk];rep(i, 0, N){if ((1 << i)&msk) {int temp = dfs(msk-(1<<i));fore(x, e[i]) {if (!(msk&(1 << x.first))) {temp += x.second;}}memo[msk] = max(memo[msk], temp);}}return memo[msk];}int main(){cin >> N >> M;memset(memo, -1, sizeof(memo));rep(i, 0, M) {int i1, i2, sc;cin >> i1 >> i2 >> sc;e[i2].pb({i1,sc});}cout << dfs((1 << N) - 1) << endl;return 0;}