Submission #1336504

#TimeUsernameProblemLanguageResultExecution timeMemory
1336504khachdulichBank (IZhO14_bank)C++20
27 / 100
1095 ms4544 KiB
#include<bits/stdc++.h>
using namespace std;
#define MASK(i) ( 1LL << (i))
#define BIT(x , i) (((x) >> (i)) & 1)


int n , m;
int a[20];
int b[20];
int sum[MASK(20) + 3];
int dp[MASK(20) + 3];

int main(){
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for(int i = 0 ; i < n ; i++){
        cin >> a[i];
    }

    for(int i = 0 ; i < m ; i++){
        cin >> b[i];
        sum[MASK(i)] = b[i];
    }


    for(int mask = 0 ; mask <MASK(m) ; mask++){
        if(__builtin_popcount(mask) >= 2){
            int tmp = mask &- mask;
            sum[mask] = sum[tmp] + sum[mask^tmp];
        }
    }

    for(int mask = 0 ; mask < MASK(m) ; mask++){
        for(int tmp = mask ; tmp >= 0 ; tmp--){
            tmp &= mask;
            for(int i = dp[mask^tmp] ; i < n ; i++){
                if(sum[tmp] == a[i]){
                    dp[mask] = max(dp[mask] , dp[mask^tmp] + 1);
                    break;
                }
            }
        }
    }

   for(int mask = 0 ; mask < MASK(m) ; mask++){
      if(dp[mask] == n){
           cout << "YES";
          return 0;
       }
   }

    //for(int i = 1 ; i < MASK(m) ; i++)cout << dp[i] << " ";


    cout << "NO";

    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...