Submission #00057
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include<bits/stdc++.h> using namespace std; #define ll long long #define INF 1000000000000000LL ll dp( int bits); int n; int a[29][29]; ll memo[1<<21]; int main(){ memset (memo,-1, sizeof (memo)); cin>>n; for ( int i=0;i<n;i++){ for ( int j=0;j<n;j++){ cin>>a[i][j]; } } cout<<dp(0)<<endl; return (0); } ll dp( int bits){ ll rec=INF,cnt=0; if (memo[bits]!=-1) return memo[bits]; for ( int i=0;i<n;i++){ cnt+=(bits>>i)&1; } if (cnt==n) return 0; for ( int i=0;i<n;i++){ if (!((bits>>i)&1)){ rec=min(rec,dp(bits|(1<<i))+a[i][cnt]); } } return memo[bits]=rec; } |
ステータス
項目 | データ |
---|---|
問題 | 0011 - 発表会 |
ユーザー名 | r1705 |
投稿日時 | 2019-04-25 18:31:14 |
言語 | C++11 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 646 Byte |
最大実行時間 | 190 ms |
最大メモリ使用量 | 17072 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 100 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
case01.in | AC | 190 ms | 16860 KB |
1
|
case02.in | AC | 133 ms | 16960 KB |
1
|
case03.in | AC | 141 ms | 17056 KB |
1
|
case04.in | AC | 160 ms | 17028 KB |
1
|
case05.in | AC | 143 ms | 16996 KB |
1
|
case06.in | AC | 144 ms | 16840 KB |
1
|
case07.in | AC | 155 ms | 16932 KB |
1
|
case08.in | AC | 134 ms | 17024 KB |
1
|
case09.in | AC | 142 ms | 16988 KB |
1
|
case10.in | AC | 152 ms | 16828 KB |
1
|
case11.in | AC | 172 ms | 16920 KB |
1
|
case12.in | AC | 163 ms | 16880 KB |
1
|
case13.in | AC | 170 ms | 16848 KB |
1
|
case14.in | AC | 178 ms | 16816 KB |
1
|
case15.in | AC | 167 ms | 16912 KB |
1
|
case16.in | AC | 170 ms | 16884 KB |
1
|
case17.in | AC | 155 ms | 16976 KB |
1
|
case18.in | AC | 185 ms | 17072 KB |
1
|
case19.in | AC | 147 ms | 16916 KB |
1
|
case20.in | AC | 143 ms | 16884 KB |
1
|
sample01.in | AC | 22 ms | 16980 KB |
1
|
sample02.in | AC | 29 ms | 16824 KB |
1
|