제출 #982849

#제출 시각아이디문제언어결과실행 시간메모리
982849dpsaveslives은행 (IZhO14_bank)C++17
52 / 100
1030 ms996 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 21; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N,M; cin >> N >> M; vector<int> arr(N),bank(M); for(int i = 0;i<N;++i) cin >> arr[i]; for(int i = 0;i<M;++i) cin >> bank[i]; vector<vector<int>> poss(N); for(int i = 0;i<N;++i){ for(int j = 1;j<(1<<M);++j){ int cur = 0; for(int k = 0;k<M;++k){ if((1<<k)&j){ cur += bank[k]; } } if(cur == arr[i]){ poss[i].push_back(j); } } } vector<bool> dp((1<<M),false); dp[0] = true; for(int i = 0;i<N;++i){ vector<bool> newdp((1<<M),false); for(int j = (1<<M)-1;j>=0;--j){ for(auto t : poss[i]){ if(t&j) continue; if(dp[j]){ //cout << j << " " << t << "\n"; newdp[j|t] = true; } } } dp = newdp; } for(int i = 0;i<(1<<M);++i){ if(dp[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...