Submission #1232131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232131		rana_azka	Bank (IZhO14_bank)	C++20	46 / 100	143 ms	119072 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];
int sum_bitmask[2000000+5];
vector<int> v[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++){
        for(int k = 0; k < m; k++){
            if((j >> k) & 1){
                sum_bitmask[j] += b[m-k];
                v[sum_bitmask[j]].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++){
        bool ada = 0;

        for(int j = 0; j <= (1 << m); j++){
            if(sum_bitmask[j] == a[i]){
                if(i == 1){
                    ada = 1;
                    break;
                }
                
                for(auto k : v[prefix[i-1]]){
                    if((j & k) == 0){
                        ada = 1;
                        break;
                    }
                }
            }
            if(ada) break;
        }

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

    cout << "YES" << endl;

    // bool ans = !v[n].empty();
    // for(int j = 0; j <= (1 << m); j++) ans |= dp[n][j];
    
    // if(ans) cout << "YES" << endl;
    // else cout << "NO" << endl;

    // for(int i = 0; i <= n; i++){
    //     for(int j = 0; j <= (1 << m); j++){
    //         cerr << j << " : " << dp[i][j] << endl;
    //     }
    //     cerr << 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: 0 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29