제출 #1198354

#제출 시각아이디문제언어결과실행 시간메모리
1198354KindaGoodGamesBank (IZhO14_bank)C++20
52 / 100
626 ms327680 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define tiii tuple<int,int,int> using namespace std; int main(){ int n,m; cin >> n >> m; vector<int> sal(n),val(m); for(int i = 0; i < n; i++){ cin >> sal[i]; } for(int i = 0; i < m; i++){ cin >> val[i]; } int p2 = (1<<m); vector<int> dp(p2,-1); vector<set<int>> left(p2); //vector<int> left(p2,sal[0]); dp[0] = 0; left[0].insert(sal[0]); for(int k = 1; k < p2; k++){ for(int i = 0; i < m; i++){ if(dp[k] >= n) break; int cur = (1 << i); if(k & cur){ bool pos = false; for(auto u : left[k-cur]){ if(u == val[i]){ pos = true; break; } } if(pos && dp[k-cur]+1 > dp[k]){ dp[k] = dp[k-cur]+1; if(dp[k] >= n) break; left[k] = {sal[dp[k]]}; }else if(dp[k-cur] > dp[k]){ dp[k] = dp[k-cur]; left[k] = left[k-cur]; for(auto u : left[k-cur]){ if(u-val[i] >= 0) left[k].insert(u-val[i]); } }else if(dp[k-cur] == dp[k]){ for(auto u : left[k-cur]){ if(u-val[i] >= 0) left[k].insert(u-val[i]); } } } } } if(dp[p2-1] == n){ 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...