結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2018-10-11 16:54:21 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 1,647 bytes |
コンパイル時間 | 986 ms |
コンパイル使用メモリ | 91,892 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 17:37:35 |
合計ジャッジ時間 | 1,606 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <cmath>#include <cstdio>#include <functional>#include <numeric>#include <stack>#include <queue>#include <map>#include <set>#include <utility>#include <sstream>#include <complex>#include <fstream>#include <bitset>#include <time.h>#include <tuple>#include <iomanip>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<ll, ll> P;typedef vector<ll> V;typedef complex<double> Point;#define PI acos(-1.0)#define EPS 1e-10const ll INF = 1e16;const ll MOD = 1e9 + 7;#define FOR(i,a,b) for(int i=(a);i<(b);i++)#define rep(i,N) for(int i=0;i<(N);i++)#define ALL(s) (s).begin(),(s).end()#define EQ(a,b) (abs((a)-(b))<EPS)#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )#define fi first#define se second#define N_SIZE (1LL << 20)#define NIL -1ll sq(ll num) { return num*num; }ll mod_pow(ll x, ll n) {if (n == 0)return 1;if (n == 1)return x%MOD;ll res = sq(mod_pow(x, n / 2));res %= MOD;if (n % 2 == 1) {res *= x;res %= MOD;}return res;}ll mod_add(ll a, ll b) { return (a + b) % MOD; }ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }ll mod_mul(ll a, ll b) { return a*b % MOD; }ll n,m;ll score[14][14];ll dp[1<<14];int main(){cin >> n >> m;rep(i,m){ll i1,i2,s;cin >> i1 >> i2 >> s;score[i1][i2] = s;}rep(i,(1<<n)){rep(j,n){if(i&(1<<j))continue;ll nxt = i | (1<<j);ll sum = dp[i];rep(k,n){if(i&(1<<k))sum += score[k][j];}dp[nxt] = max(dp[nxt],sum);}}cout << dp[(1<<n)-1] << endl;}