結果
問題 | No.50 おもちゃ箱 |
ユーザー |
![]() |
提出日時 | 2020-09-07 00:54:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,233 bytes |
コンパイル時間 | 1,900 ms |
コンパイル使用メモリ | 176,976 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-29 07:57:23 |
合計ジャッジ時間 | 3,619 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define all(x) (x).begin(), (x).end() using namespace std; using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; int n, m; VI a, b; int ans = 100; VVI division; void dfs(int k, int nxt=0) { if (k == n) { VI s(nxt); rep(i, nxt) for(int v: division[i]) s[i] += v; sort(s.rbegin(), s.rend()); bool ok = true; rep(i, nxt) { if (s[i] > b[i]) { ok = false; break; } } if (ok) { chmin(ans, nxt); } return; } rep(i, nxt) { division[i].push_back(a[k]); dfs(k + 1, nxt); division[i].pop_back(); } if (nxt < m) { division[nxt].push_back(a[k]); dfs(k + 1, nxt + 1); division[nxt].pop_back(); } } int main() { cin >> n; a.resize(n); rep(i, n) cin >> a[i]; cin >> m; division.resize(m); b.resize(m); rep(i, m) cin >> b[i]; sort(b.rbegin(), b.rend()); dfs(0); if (ans == 100) ans = -1; cout << ans << endl; }