Submission #1232436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232436		rana_azka	Bank (IZhO14_bank)	C++20	100 / 100	302 ms	90064 KiB

bank

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

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 20;

int n, m, k;
int a[MAXN+5];
int b[MAXN+5];
int prefix[MAXN+5];
int dp[MAXN+5][2000000];
vector<int> bm[20000+5];

void mulaidarinol(){}

void solve(){
	cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];

    for(int j = 0; j <= (1 << m); j++){
        int temp = 0;
        for(int k = 0; k < m; k++){
            if((j >> k) & 1){
                temp += b[m-k];
            }
        }
        bm[temp].push_back(j);
    }
    
    for(int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + a[i];
    
    // for(int j = 0; j <= (1 << m); j++) dp[0][j] = 1;

	for(int i = 1; i <= n; i++){
        // cerr << "i : " << i << endl;
        bool ada = 0;
        for(auto j : bm[a[i]]){
            // cerr << " j : " << j << endl;

            if(i == 1){
                dp[i][j] = 1;
                ada = 1;
            }else{
                for(auto k : bm[prefix[i-1]]){
                    // cerr << "  k : " << k << endl;
                    if((j & k) == 0 && dp[i-1][k]){
                        dp[i][j|k] = 1;
                        ada = 1;
                    }
                }
            }
        }

        if(!ada){
            cout << "NO" << endl;
            return ;
        }
    }

    cout << "YES" << endl;
}

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

    int tc = 1;
    // cin >> tc;
    while(tc--){
        // mulaidarinol();
        solve();
        cerr << endl;
    }

    return 0;
}

/*
1 5
8
4 2 5 1 3

2 6
9 10
5 4 8 6 3 11

2 8
9 10
5 4 8 6 3 11 2 5
*/

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