結果
問題 | No.50 おもちゃ箱 |
ユーザー |
|
提出日時 | 2016-11-15 18:06:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 5,000 ms |
コード長 | 1,203 bytes |
コンパイル時間 | 996 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 22:00:58 |
合計ジャッジ時間 | 2,176 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) #define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i)) using namespace std; template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); } template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); } int main() { // input int n; cin >> n; vector<int> a(n); repeat (i,n) cin >> a[i]; int m; cin >> m; vector<int> b(m); repeat (j,m) cin >> b[j]; // compute vector<int> sum(1<<n); repeat_from (s,1,1<<n) sum[s] = sum[s&(s-1)] + a[__builtin_ctz(s)]; sort(b.rbegin(), b.rend()); vector<vector<bool> > dp = vectors(bool(), m+1, 1<<n); dp[0][0] = true; repeat (j,m) { repeat (k,1<<n) if (sum[k] <= b[j]) { repeat (s,1<<n) { if (dp[j][s]) dp[j+1][s|k] = true; } } } // output int ans = -1; repeat (j,m+1) { if (dp[j][(1<<n)-1]) { ans = j; break; } } cout << ans << endl; return 0; }