結果
問題 | No.50 おもちゃ箱 |
ユーザー |
![]() |
提出日時 | 2014-11-07 16:07:32 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 811 bytes |
コンパイル時間 | 614 ms |
コンパイル使用メモリ | 57,620 KB |
実行使用メモリ | 7,680 KB |
最終ジャッジ日時 | 2024-12-31 06:46:34 |
合計ジャッジ時間 | 3,555 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 WA * 2 |
ソースコード
#include <iostream> #include <algorithm> #define INF (2 << 28) using namespace std; int n, m; int a[11], b[11], dp[1<<10][1<<10]; int rec(int toy, int used){ //cout << toy << " " << used << endl; if(toy == 0) return __builtin_popcount(used); if(dp[toy][used]) return dp[toy][used]; int ret = INF; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(a[i] <= b[j] && toy >> i & 1){ b[j] -= a[i]; ret = min(ret, rec(~(1 << i) & toy, used | (1 << j))); b[j] += a[i]; } } } return dp[toy][used] = ret; } int main(){ cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; cin >> m; for(int i = 0; i < m; i++) cin >> b[i]; int d = rec((1<<n)-1, 0); if(d == INF) cout << -1 << endl; else cout << d << endl; }