제출 #68552

#제출 시각아이디문제언어결과실행 시간메모리
68552quoriess은행 (IZhO14_bank)C++14
71 / 100
1078 ms33952 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int lli; int main(){ int n,m; cin>>n>>m; vector<int> salary,banks; for (int i = 0; i < n; i++) { int a; cin>>a; salary.push_back(a); } for (int j = 0; j < m; j++) { int a; cin>>a; banks.push_back(a); } /* 2 4 3 6 5 1 2 1 */ vector<vector<bitset<20> > > sncler(n,vector<bitset<20> >()); for (int i = 0; i < 1<<m; i++) { bitset<20> smd(i); int tplm=0; for (int j = 0; j < m; j++) { if(smd[j]) tplm+=banks[j]; } for(int j=0;j<n;j++){ if(salary[j]==tplm) sncler[j].push_back(smd); } } int mstb=1<<m; bool dp[n][mstb]; set<int> bakilacaklar; for(int i=0;i<n;i++){ for(int j=0;j<mstb;j++)dp[i][j]=0; } for(auto j:sncler[0]){ dp[0][j.to_ulong()]=1; bakilacaklar.insert(j.to_ulong()); } for (int i = 1; i < n; i++) { set<int> nb; for(auto k:bakilacaklar){ for (auto j: sncler[i]) { if((k&j.to_ulong())==0){ dp[i][k^j.to_ulong()]=dp[i-1][k]||dp[i][k^j.to_ulong()]; if(dp[i][k^j.to_ulong()])nb.insert(k^j.to_ulong()); } } } bakilacaklar=nb; } bool ans=0; for(int i=1;i<mstb;i++)if(dp[n-1][i])ans=true; cout << (ans?"YES":"NO")<<"\n"; 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...