제출 #170039

#제출 시각아이디문제언어결과실행 시간메모리
170039tselmegkh은행 (IZhO14_bank)C++14
71 / 100
1086 ms564 KiB
#include<bits/stdc++.h> using namespace std; int a[25], b[25], n, m; bool dp[25][(1 << 21)]; bool vis[25][(1 << 21)]; inline bool go(int v, int mask, int leftsum){ if(v == n){ return 1; } if(vis[v][mask])return dp[v][mask]; vis[v][mask] = 1; bool possible = 0; int totsum = 0; for(int i = 0; i < m; i++){ if(!(mask & (1 << i)))totsum += b[i]; } if(totsum < leftsum){ return 0; } for(int i = 0; i < (1 << m); i++){ int sum = 0; int tmp = i; while(tmp){ int lsone = (tmp) & (-tmp); int j = __builtin_ctz(lsone); sum += b[j]; tmp -= lsone; } if(sum == a[v] && !(i & mask)){ possible |= go(v + 1, mask | i, sum - a[v]); } } return dp[v][mask] = possible; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m; int sum = 0; for(int i = 0; i < n; i++){ cin >> a[i]; sum += a[i]; } //sort(a, a + n, greater<int>()); for(int i = 0; i < m; i++){ cin >> b[i]; } if(go(0, 0, sum)){ cout << "YES\n"; }else{ cout << "NO\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...