結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2019-04-05 19:14:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 816 bytes |
コンパイル時間 | 640 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-12 23:43:29 |
合計ジャッジ時間 | 1,322 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <algorithm>#include <iostream>#include <iomanip>#include <cstring>#include <string>#include <vector>#include <queue>#include <cmath>#include <stack>#include <set>#include <map>typedef long long ll;using namespace std;int main(){int N,M;cin >> N >> M;int sco[N][N];fill(sco[0],sco[N],0);for(int i=0;i<M;i++){int x,y,s;cin >> x >> y >> s;sco[x][y] = s;}int dp[1 << N];fill(dp,dp+(1<<N),0);for(int msk=0 ; msk<(1<<N) ; msk++){for(int i=0;i<N;i++){if(!(msk & (1 << i))){int sum = 0;for(int j=0;j<N;j++){if(msk & (1 << j)){sum += sco[i][j];}}dp[msk + (1 << i)] = max(dp[msk + (1 << i)], dp[msk] + sum);}}}cout << dp[(1 << N) - 1] << endl;return 0;}