제출 #677716

#제출 시각아이디문제언어결과실행 시간메모리
677716ismayil은행 (IZhO14_bank)C++17
100 / 100
535 ms131128 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; vector<vector<int>> dp, cost; vector<int> a, b; int n, m; int solve(int mask, int i){ if(i == n) return 1; if(dp[mask][i] != -1) return dp[mask][i]; for(auto s : cost[a[i]]){ if((s & mask) == s){ if(solve(mask ^ s, i + 1)){ return dp[mask][i] = 1; } } } return dp[mask][i] = 0; } int main(){ cin>>n>>m; a = vector<int>(n); b = vector<int>(m); dp = vector<vector<int>>((1<<m), vector<int>(n, -1)); for(auto& i : a) cin>>i; for(auto& i : b) cin>>i; cost.resize(30005); for (int mask = 0; mask < (1<<m); mask++) { int total = 0; for (int i = 0; i < m; i++) { if(!(mask & (1<<i))) continue; total += b[i]; } cost[total].push_back(mask); } cout<<(solve((1<<m) - 1, 0) ? "YES" : "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...