Submission #1263735

#TimeUsernameProblemLanguageResultExecution timeMemory
1263735backBank (IZhO14_bank)C++20
100 / 100
276 ms34372 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n); for (int &x : a) cin >> x; vector<int> b(m); for (int &x : b) cin >> x; int ALL = 1 << m; vector<int> sum(ALL, 0); for (int mask = 1; mask < ALL; mask++) { int lb = __builtin_ctz(mask); sum[mask] = sum[mask ^ (1<<lb)] + b[lb]; } // danh sách submask có tổng = x unordered_map<int, vector<int>> subs; for (int mask = 0; mask < ALL; mask++) { subs[sum[mask]].push_back(mask); } vector<vector<char>> dp(n+1, vector<char>(ALL, 0)); dp[0][0] = 1; for (int i = 0; i < n; i++) { for (int mask = 0; mask < ALL; mask++) if (dp[i][mask]) { for (int sub : subs[a[i]]) { if ((mask & sub) == 0) { dp[i+1][mask | sub] = 1; } } } } bool ok = false; for (int mask = 0; mask < ALL; mask++) { if (dp[n][mask]) ok = true; } cout << (ok ? "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...