結果
問題 | No.50 おもちゃ箱 |
ユーザー |
|
提出日時 | 2014-10-27 01:30:47 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,440 bytes |
コンパイル時間 | 593 ms |
コンパイル使用メモリ | 69,704 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 20:44:04 |
合計ジャッジ時間 | 1,640 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; void update(pair<int,int>& a, pair<int, int> b){ if(b.first < a.first){ a = b; } else if(b.first == a.first && b.second > a.second){ a = b; } } int main(){ int N, M; cin >> N; vector<int> A(N); for(int i=0;i<N;i++)cin >> A[i]; cin >> M; vector<int> B(M); for(int i=0;i<M;i++)cin >> B[i]; sort(B.rbegin(), B.rend()); const pair<int,int> none = make_pair(1000, -1);; vector< pair<int,int> > dp(1 << N, none); dp[0] = make_pair(0, B[0]); for(int S=0;S<1<<N;S++){ if(dp[S] == none)continue; int k = dp[S].first; int rest = dp[S].second; for(int i=0;i<N;i++){ if((S >> i) & 1)continue; if(A[i] > rest)continue; update(dp[S | (1 << i)], make_pair(k, rest - A[i])); } if(k + 1 < M){ for(int i=0;i<N;i++){ if((S >> i) & 1)continue; if(A[i] > B[k + 1])continue; update(dp[S | (1 << i)], make_pair(k + 1, B[k + 1] - A[i])); } } } int res = -1; if(dp[(1 << N) - 1] != none){ res = dp[(1 << N) - 1].first + 1; } cout << res << endl; return 0; }