# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
39100 | 2018-01-09T09:56:37 Z | mrtsima22 | Bank (IZhO14_bank) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; int b[1000003],n,m,s[1000003],s[1000003]; int a[1000003],d[23][1000003]; string ans="NO"; int main(){std::ios::sync_with_stdio(false); cin>>n>>m; for(int i=0;i<n;i++) { cin>>b[i]; b[i]+=b[i-1]; } for(int i=0;i<m;i++) { cin>>a[i]; } for(int i=0;i<(1<<m);i++) { for(int j=0;j<m;j++) { if(!((i>>j)&1)) { s[i|(1<<j)]=s[i]+a[j]; } } } d[0][0]=1; for(int i=0;i<=n;i++) { for(int j=0;j<(1<<m);j++) { if(!d[i][j]) { continue; } if(i==n) { ans="YES"; break; } if(b[i]==s[j]) { d[i+1][j]=1; } for(int t=0; t<m; t++) { if(!((j>>t)&1)) { d[i][j|(1<<t)]=1; } } } } cout<<ans<<endl; } /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */