Submission #1248321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248321		e_n1cat_	Bank (IZhO14_bank)	C++20	52 / 100	1093 ms	1768 KiB

bank

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

#define ll long long
#define int ll

const int sz = 25;
const int mod = 1e9 + 9;

int a[sz], b[sz];
bool dp[20+1][(1<<20)];

void solve(){
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    vector<int> v[25];
    dp[0][0] = true;
    for(int mask = 1; mask < (1 << m); mask++){
        dp[0][mask] = true;
        int cem = 0;
        for(int j = 0; j < m; j++){
            if((1 << j) & mask) cem += b[j];
        }
        for(int i = 1; i <= n; i++){
            if(a[i] == cem) v[i].push_back(mask);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int mask = 1; mask < (1<<m); mask++){
            for(auto mask2: v[i]){
                if((mask2 & mask) == mask2){
                    dp[i][mask] |= dp[i-1][mask ^ mask2];
                }
                if(dp[i][mask]) break;
            }
        }
    }
    cout << (dp[n][(1<<m) - 1] ? "YES" : "NO") << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); solve();
}

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