제출 #502458

#제출 시각아이디문제언어결과실행 시간메모리
502458clams은행 (IZhO14_bank)C++17
100 / 100
718 ms8736 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 20; int n, m, a[N + 5], b[N + 5], dp[(1 << N) + 5]; /// dp[s] = maximum number of people covered with mask s of b[] vector<int> adj[N + 5]; /// adj[j] = the masks of b[] that sum to a[j] signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; for (int s = 0; s < (1 << m); s++) { int sum = 0; for (int i = 0; i < m; i++) { if ((s >> i) & 1) { sum += b[i]; } } for (int j = 0; j < n; j++) { if (sum == a[j]) { adj[j].push_back(s); } } } dp[0] = 1; for (int j = 0; j < n; j++) { for (int s = (1 << m) - 1; s >= 0; s--) { if (dp[s] > 0) { for (int t : adj[j]) { if (s & t) continue; int x = s | t; dp[x] = max(dp[x], dp[s] + 1); if (dp[x] > n) { cout << "YES"; return 0; } } } } } 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...