Submission #1228946

#TimeUsernameProblemLanguageResultExecution timeMemory
1228946MinhKienBank (IZhO14_bank)C++20
100 / 100
328 ms8568 KiB
#include <iostream> #include <vector> using namespace std; const int N = 22; const int M = 1010; const int LIM = (1 << 20) + 10; int n, m, a[N], b[N]; vector <int> v[M]; bool dp[2][LIM]; int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 0; i < m; ++i) cin >> b[i]; for (int i = 0; i < (1 << m); ++i) { int sum = 0; for (int j = 0; j < m; ++j) { if (i >> j & 1) sum += b[j]; if (sum > 1000) break; } if (sum <= 1000) v[sum].push_back(i); } dp[1][(1 << m) - 1] = true; for (int i = 1; i <= n; ++i) { int b = i & 1; fill_n(dp[b ^ 1], (1 << m), false); for (int mask = 0; mask < (1 << m); ++mask) { if (!dp[b][mask]) continue; for (int z: v[a[i]]) { if ((mask & z) == z) dp[b ^ 1][mask ^ z] = true; } } } int b = (n & 1) ^ 1; for (int i = 0; i < (1 << m); ++i) { if (dp[b][i]) { cout << "YES\n"; return 0; } } cout << "NO\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...