Submission #943237

#TimeUsernameProblemLanguageResultExecution timeMemory
943237mannshah1211Bank (IZhO14_bank)C++14
52 / 100
1090 ms7168 KiB
/** * author: hashman * created: **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif int32_t main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> a(n), b(m); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; } vector<vector<int>> masks(1001); for (int i = 0; i < (1 << m); i++) { int sum = 0; for (int j = 0; j < m; j++) { if (i & (1 << j)) sum += b[j]; } if (sum <= 1000) masks[sum].push_back(i); } vector<vector<bool>> dp(n + 1, vector<bool>((1 << m))); for (int i = 0; i < (1 << m); i++) { dp[0][i] = true; } for (int i = 1; i <= n; i++) { for (int j = 0; j < (1 << m); j++) { for (int mask : masks[a[i - 1]]) { if ((j & mask) == mask) { dp[i][j] = dp[i][j] || dp[i - 1][j ^ mask]; } } } } if (dp[n][(1 << m) - 1]) cout << "YES\n"; else 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...