Submission #916614

#TimeUsernameProblemLanguageResultExecution timeMemory
916614atomBank (IZhO14_bank)C++17
71 / 100
1041 ms144176 KiB
#include "bits/stdc++.h" // @JASPER'S BOILERPLATE using namespace std; using ll = long long; #ifdef JASPER #include "debug.h" #else #define debug(...) 166 #endif const int N = 22; int n, m; int a[N], b[N]; int dp[N][1 << N]; vector <int> adj[1 << N]; // dp(i, x): (1..i person with mask x of bank notes); signed main() { cin.tie(0) -> sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < n; ++i) cin >> a[i]; for (int j = 0; j < m; ++j) cin >> b[j]; for (int i = 0; i < n; ++i) { int target = a[i]; for (int msk = 0; msk < (1 << m); ++msk) { int sum = 0; for (int j = 0; j < m; ++j) { if (msk & (1 << j)) { sum += b[j]; } } if (sum == target) adj[i].push_back(msk); } } dp[0][0] = 1; for (int i = 0; i < n; ++i) { for (int msk = 0; msk < (1 << m); ++msk) { if (!dp[i][msk]) continue; for (int valid_msk : adj[i]) { if (!(valid_msk & msk)) dp[i + 1][msk | valid_msk] = 1; } } } bool ans = 0; for (int msk = 0; msk < (1 << m); ++msk) { if (dp[n][msk]) { ans = 1; break; } } cout << (ans? "YES\n" : "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...