제출 #873786

#제출 시각아이디문제언어결과실행 시간메모리
873786Irate은행 (IZhO14_bank)C++14
52 / 100
1094 ms25692 KiB
#include<bits/stdc++.h> using namespace std; int n, m; vector<int>a, b; vector<vector<int>>lookup; int dp[21][(1 << 20)]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; a.resize(n); b.resize(m); lookup.resize(2e4 + 3); for(int i = 0;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 & (1 << j))){ sum += b[j]; } } lookup[sum].push_back(i); } for(int j = 0;j < (1 << m);++j){ dp[n][j] = 1; } for(int i = n - 1;i >= 0;--i){ for(int mask = 0;mask < (1 << m);++mask){ for(int &submask : lookup[a[i]]){ if((mask & submask) == submask){ dp[i][mask] |= dp[i + 1][mask ^ submask]; } } } } if(dp[0][(1 << m) - 1]){ 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...