제출 #676316

#제출 시각아이디문제언어결과실행 시간메모리
676316murad_2005은행 (IZhO14_bank)C++17
0 / 100
58 ms84808 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int, int> #define piii pair<pii, int> #define pllll pair<ll, ll> #define pb push_back #define all(v) v.begin(), v.end() #define size(v) v.size() #define INF 2e18 #define f first #define s second using namespace std; const int up = 20; int n, m; vector<int>costMask[20005]; vector<vector<bool>>dp((1 << up), vector<bool>(n)); vector<int>a, b; bool Bank(int mask, int i){ if(i == n + 1) return true; if(dp[mask][i]) return dp[mask][i]; for(int Submask : costMask[a[i]]){ if((mask & Submask) == Submask){ if(Bank(mask ^ Submask, i - 1)){ return dp[mask][i] = true; } } } return dp[mask][i] = false; } void solve(){ cin >> n >> m; a.resize(n + 1), b.resize(m + 1); for(int i = 0; i < n; ++i){ cin >> a[i]; }for(int i = 0; i < m; ++i){ cin >> b[i]; } for(int mask = 0; mask < (1 << m); ++mask){ int Total = 0; for(int i = 0; i < m; ++i){ if(mask & (1 << i)){ Total += b[i + 1]; } } costMask[Total].pb(mask); } for(int mask = 0; mask < (1 << m); mask++){ dp[0][mask] = true; } if(Bank((1 << m) - 1, 1)) cout << "YES\n"; else cout << "NO\n"; } int main(){ int t; t = 1; //cin >> t; while(t--){ solve(); } 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...