제출 #1232150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232150		rana_azka	은행 (IZhO14_bank)	C++20	71 / 100	1099 ms	138344 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> bm[20000+5];
vector<int> v[MAXN+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];
                bm[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++){
        // cerr << "i : " << i << endl;
        for(auto j : bm[a[i]]){
            // cerr << " j : " << j << endl;
            if(i == 1){
                v[i].push_back(j);
            }else{
                for(auto k : v[i-1]){
                    // cerr << "  k : " << k << endl;
                    if((j & k) == 0){
                        v[i].push_back(j | k);
                    }
                }
            }
        }

        if(v[i].empty()){
            cout << "NO" << endl;
            return ;
        }
    }

    cout << "YES" << endl;

    // bool ans = !bm[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: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29