Submission #1231866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231866		rana_azka	은행 (IZhO14_bank)	C++20	19 / 100	263 ms	15872 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 dp[MAXN+5][2000000];

void mulaidarinol(){}

void cek(int idx, int val, int mask){
    for(int i = 0; i < m; i++){
        if(mask >> i) continue;
        if(val - b[m-i] < 0) continue;

        int tmp_val = val - b[m-i];
        int tmp_mask = mask | (1 << i);
        // cerr << "mask : " << mask << ' ' << (1 << i) << endl;
        // cerr << tmp_val << ' ' << tmp_mask << endl;
        if(tmp_val == 0){
            dp[idx][tmp_mask] = 1;
            continue;
        }

        cek(idx, tmp_val, tmp_mask);
    }
}

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++) dp[0][j] = 1;
	
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= (1 << m); j++){
            if(dp[i-1][j] == 0) continue;
            
            cek(i, a[i], j);
        }
    }
    
    bool ans = 0;
    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
*/

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