Submission #1269331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269331		mj5aif	Bank (IZhO14_bank)	C++20	100 / 100	427 ms	25532 KiB

bank

/**
*  Problem Name: Bank
*  Author: MJ
*  Created: 13 September 2025, Saturday (03:40:33)...
**/

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define nl '\n' 

void answer_to_the_question(){
   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> sum(1<<m),mask[20003];
   for(int k=1;k<(1<<m);k++){
      for(int i=0;i<m;i++)if(k&(1<<i)){
         sum[k]+=b[i];
      }
      mask[sum[k]].push_back(k);
   }

   vector<vector<bool>> dp(n,vector<bool> (1<<m,false));
   for(auto &i: mask[a[0]]) dp[0][i]=true;

   int tm=a[0];
   for(int i=1;i<n;i++){
      tm+=a[i];

      for(auto &k: mask[tm]){

         for(auto &j: mask[a[i]]){
            if((k&j)==j){
               dp[i][k]=(dp[i][k] || dp[i-1][j^k]);
            }
         }
      }
   }

   for(int k=0;k<(1<<m);k++)if(dp[n-1][k]){
      cout<<"YES"<<nl;
      exit(0);
   }

   cout<<"NO"<<nl;
}

int32_t main(){
   ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

   answer_to_the_question();

   return 0;
}

// .... headlock, You Know You'r better than this.

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