제출 #1171846

#제출 시각아이디문제언어결과실행 시간메모리
1171846nt_nhanBank (IZhO14_bank)C++20
52 / 100
1095 ms10856 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define el '\n' int n, m, a[21], b[21]; bool dp[21][1 << 21]; int sum[1 << 21]; vector<int> pre[21]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int j = 1; j <= m; ++j) { cin >> b[j]; } for (int mask = 0; mask < (1 << m); ++mask) { for (int j = 0; j < m; ++j) { if ((mask >> j) & 1) continue; sum[mask | (1 << j)] = sum[mask] + b[j + 1]; } dp[0][mask] = true; } pre[0].push_back(0); for (int i = 1; i <= n; ++i) { for (int mask = 0; mask < (1 << m); ++mask) { if (a[i] == sum[mask]) { pre[i].push_back(mask); } } } for (int i = 1; i <= n; ++i) { for (int mask = 0; mask < (1 << m); ++mask) { if (dp[i - 1][mask]) { for (int p : pre[i]) { if (p & mask) continue; dp[i][mask | p] = 1; } } } } for (int mask = 0; mask < (1 << m); ++mask) { dp[n][(1 << m) - 1] |= dp[n][mask]; } cout << (dp[n][(1 << m) - 1] ? "YES" : "NO"); 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...