結果
問題 | No.519 アイドルユニット |
ユーザー |
![]() |
提出日時 | 2020-12-14 02:23:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 1,000 ms |
コード長 | 758 bytes |
コンパイル時間 | 1,722 ms |
コンパイル使用メモリ | 179,828 KB |
実行使用メモリ | 6,248 KB |
最終ジャッジ日時 | 2024-09-20 00:23:03 |
合計ジャッジ時間 | 3,547 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i, n) for(int i = 0; i < (int)(n); i++) int main(){ int N; cin >> N; int F[N][N]; rep(i, N) rep(j, N){ cin >> F[i][j]; F[i][j]++; } unordered_map<int, int> dp; queue<int> que; que.push(0); while(!que.empty()){ int c = que.front(); que.pop(); int j = 0; while((c & (1<<j))) j++; for(int k = j + 1; k < N; k++){ if(c & (1<<k)) continue; int d = c + (1<<j) + (1<<k); if(dp[d] < dp[c] + F[j][k]){ dp[d] = dp[c] + F[j][k]; if(d != (1<<N) - 1) que.push(d); } } } cout << dp[(1<<N) - 1] - N / 2 << endl; return 0; }