Submission #887733

#TimeUsernameProblemLanguageResultExecution timeMemory
887733viwlesxqBank (IZhO14_bank)C++17
44 / 100
1068 ms596 KiB
#include <bits/stdc++.h> using namespace std; typedef int64_t ll; #define all(x) x.begin(), x.end() #define size(x) (int)x.size() template<class S, class T> bool chmin(S &a, const T &b) { return (a > b ? (a = b) == b : false); } template<class S, class T> bool chmax(S &a, const T &b) { return (a < b ? (a = b) == b : false); } const ll inf = 1e18; const int mod = 1e9 + 7; int n, m; vector<int> a, b, g[20]; bool dfs(int v, int used) { if (v == (1 << n) - 1) { return true; } bool res = false; for (int i = 0; i < n; ++i) { if (v >> i & 1) { continue; } for (int to : g[i]) { if (used & to) { continue; } res |= dfs(v ^ (1 << i), used | to); } } return res; } signed main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m; a.resize(n), b.resize(m); for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < m; ++i) { cin >> b[i]; } for (int mask = 0; mask < (1 << m); ++mask) { int sum = 0; for (int i = 0; i < m; ++i) { if (mask >> i & 1) { sum += b[i]; } } for (int i = 0; i < n; ++i) { if (sum == a[i]) { g[i].push_back(mask); } } } cout << (dfs(0, 0) ? "YES" : "NO"); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...