Submission #863453

#TimeUsernameProblemLanguageResultExecution timeMemory
863453grateBank (IZhO14_bank)C++17
0 / 100
0 ms600 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pll pair<ll, ll> #define ppll pair<pll, ll> #define fll(i, n) for (ll i =0 ; i < n; i++) #define vll vector<ll> #define prtv(V) fll(i, V.size()) cout << V[i] << " "; cout << '\n'; ll INF = 2e18; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ll n, m; cin >> n >> m; vll A(n), B(m); fll(i, n) cin >> A[i]; ll S = 0; fll(i, m) { cin >> B[i]; S += B[i]; } sort(B.begin(), B.end(), [](ll a, ll b) { return a > b; }); vector<pll> ans(1<<n, {0, INF}); ans[0] = {m, 0}; fll(s, (1<<n)) { fll(i, n) { if (!(s&(1<<i))) { ll sum = 0, j = 0; ll k = ans[s].second; ll remNotes = ans[s].first; while (j < m && A[i] > sum) { if ((k & (1<<j) )|| (B[j]+sum > A[i])) { j++; continue; } sum += B[j]; remNotes--; k = k & (1<<j); j++; } if (sum < A[i]) continue; if (ans[s|(1<<i)].first < remNotes) ans[s|(1<<i)] = {remNotes, k}; } } } if (ans[(1<<n)-1].second == INF) cout << "NO\n"; else cout << "YES\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...