제출 #656384

#제출 시각아이디문제언어결과실행 시간메모리
656384boykut은행 (IZhO14_bank)C++14
71 / 100
1095 ms10188 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 22; int a[N], b[N], dp[N][1<<N], n, m; vector<int> can[1001]; int main() { cin.tie()->sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; } if (n>m) return cout << "NO", 0; int mx = *max_element(a, a+n); for (int mask = 0; mask < (1<<m); mask++) { int s = 0; for (int i = 0; i < m; i++) { if (((mask>>i)&1)) s += b[i]; } if (s <= mx) can[s].push_back(mask); } for (int mask : can[a[0]]) dp[0][mask] = 1; for (int i = 1; i < n; i++) { for (int mask = 0; mask < (1<<m); mask++) { for (int p : can[a[i]]) { if ((mask & p) == p) { dp[i][mask] |= dp[i-1][mask^p]; } } } } for (int mask = 0; mask < (1<<m); mask++) { if (dp[n-1][mask] == 1) return cout << "YES", 0; } return cout << "NO", 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...