Submission #1215410

#TimeUsernameProblemLanguageResultExecution timeMemory
1215410bbldrizzyBank (IZhO14_bank)C++20
19 / 100
145 ms6812 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> vals(n); vector<int> notes(m); for (int &u: vals) cin >> u; for (int &u: notes) cin >> u; vector<vector<int>> sum(1001, vector<int>()); for (int i = 1; i < (1<<m); i++) { vector<int> nds; int tmp = i; for (int j = 0; j < m; j++) { if (tmp&1) nds.push_back(j); tmp = tmp >> 1; } int tsum = 0; for (int u: nds) { tsum += notes[u]; } if (tsum <= 1000) sum[tsum].push_back(i); // for (int u: nds) { // cout << u << " "; // } // cout << "\n"; } vector<vector<int>> dp(1<<n); for (int i = 0; i < n; i++) { dp[1<<i] = sum[vals[i]]; } for (int i = 0; i < (1<<n); i++) { vector<int> nds; int tmp = i; for (int j = 0; j < m; j++) { if (tmp&1) nds.push_back(j); tmp = tmp >> 1; } if (nds.size() == 1) continue; for (int i = 0; i < nds.size(); i++) { vector<int> maskz = dp[1<<nds[i]]; vector<int> maskz2 = dp[i ^ (1<<nds[i])]; for (int u: maskz) { for (int k: maskz2) { if (u&k == 0) { dp[i].push_back(u||k); } } } } } if (dp[(1<<n) - 1].size() > 0) { cout << "YES"; } else { cout << "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...