Submission #915074

#	Time	Username	Problem	Language	Result	Execution time	Memory
915074		Aiperiii	Bank (IZhO14_bank)	C++14	100 / 100	384 ms	145588 KiB

bank

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e6;
int dp[30][N];
signed main(){
   int n,m;
   cin>>n>>m;
   vector <int> a(n),b(m);
   for(int i=0;i<n;i++){
     cin>>a[i];
   }
   for(int i=0;i<m;i++){
     cin>>b[i];
   }
   vector <int> ok[n];
   for(int mask=0;mask<(1<<m);mask++){
     int x=0;
     for(int j=0;j<m;j++){
         if((mask & (1<<j))!=0)x+=b[j];
     }
      for(int i=0;i<n;i++){
         if(a[i]==x)ok[i].pb(mask);
      }
   }
   for(auto x : ok[0])dp[0][x]=1;
   for(int i=1;i<n;i++){
      for(int mask=0;mask<(1<<m);mask++){
         if(!dp[i-1][mask])continue;
         for(auto x : ok[i]){
            if((mask&x)==0 && dp[i-1][mask])dp[i][(mask+x)]=1;
         }
      }
   }
   bool ans=0;
   for(int i=0;i<(1<<m);i++){
      //cout<<dp[n-1][i]<<"\n";
      if(dp[n-1][i]==1)ans=1;
   }
   if(ans)cout<<"YES\n";
   else cout<<"NO\n";
}
/*
 2 6
 9 10
 5 4 8 6 3 11
 */

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29