Submission #830995

#TimeUsernameProblemLanguageResultExecution timeMemory
830995alex_2008Bank (IZhO14_bank)C++14
100 / 100
100 ms8612 KiB
#include <iostream> #include <algorithm> #include <set> using namespace std; const int N = 20; int a[N], b[N]; pair <int, int> dp[(1 << N)]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; } dp[0] = {0, 0}; for (int i = 1; i < (1 << m); i++) { dp[i] = {-1, -1}; pair <int, int> ans = {-1, -1}; for (int j = 0; j < m; j++) { if (i & (1 << j)) { if (dp[i ^ (1 << j)] != make_pair(-1, -1)) { pair <int, int> cur_ans = {-1, -1}; pair <int, int> cur = dp[i ^ (1 << j)]; if (cur.second + b[j] > a[cur.first]) { continue; } if (cur.second + b[j] == a[cur.first]) { cur_ans = {cur.first + 1, 0}; } else { cur_ans = {cur.first, cur.second + b[j]}; } ans = max(ans, cur_ans); } } } dp[i] = ans; if (dp[i].first == n) { cout << "YES\n"; return 0; } } cout << "NO\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...