結果
問題 | No.519 アイドルユニット |
ユーザー |
|
提出日時 | 2017-06-02 02:14:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 61 ms / 1,000 ms |
コード長 | 690 bytes |
コンパイル時間 | 1,412 ms |
コンパイル使用メモリ | 168,496 KB |
実行使用メモリ | 69,120 KB |
最終ジャッジ日時 | 2024-10-03 03:59:27 |
合計ジャッジ時間 | 3,035 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second int n; int f[24][24]; const int N=1<<24; int dp[N]; int dfs(int s) { if(s == (1<<n)-1) return 0; if(dp[s]>=0) return dp[s]; int ret=0; int i=0; while(s>>i&1) ++i; for(int j=i+1; j<n; ++j)if(!(s>>j&1)) { int ns = s|(1<<i)|(1<<j); ret = max(ret,dfs(ns)+f[i][j]); } return dp[s]=ret; } int main() { cin >>n; rep(i,n)rep(j,n) cin >>f[i][j]; memset(dp,-1,sizeof(dp)); cout << dfs(0) << endl; return 0; }