제출 #676325

#제출 시각아이디문제언어결과실행 시간메모리
676325murad_2005은행 (IZhO14_bank)C++14
19 / 100
134 ms118212 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<int>>dp((1 << up), vector<int>(n + 1)); vector<int>a, b; int Bank(int mask, int i){ if(i == 0) return 1; if(dp[mask][i] != -1) return dp[mask][i]; for(int Submask : costMask[a[i]]){ if((mask & Submask) == Submask){ if(Bank(mask ^ Submask, i - 1)){ return dp[mask][i] = 1; } } } return dp[mask][i] = 0; } void solve(){ cin >> n >> m; a.resize(n + 1), b.resize(m + 1); for(int i = 1; i <= n; ++i){ cin >> a[i]; }for(int i = 1; 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++){ for(int i = 1; i <= n; ++i){ dp[mask][i] = -1; } } if(Bank((1 << m) - 1, n)) 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...