Submission #1272920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272920		hiepsimauhong	은행 (IZhO14_bank)	C++20	100 / 100	145 ms	1468 KiB

bank

#include <bits/stdc++.h>

using namespace std;

#define FOR(I, L, R) for(int I(L) ; I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R) ; I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define quickly ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


const int N = 20;

int n, m;
int a[N], b[N];
bool dp[1 << N];
vector<int> choose[N];

void back_track(int i, int mask){
        if(dp[mask]) return;
        dp[mask] = 1;
        if(i == n){
                cout << "YES";
                exit(0);
        }

        FOA(sub, choose[i]){
                if((sub & mask) == 0){
                        back_track(i + 1, mask ^ sub);
                }
        }
}

signed main(){ quickly
        cin >> n >> m;

        FOR(i, 0, n - 1){
                cin >> a[i];
        }

        FOR(i, 0, m - 1){
                cin >> b[i];
        }

        FOR(mask, 1, (1 << m) - 1){
                int sum = 0;
                FOR(i, 0, m - 1){
                        if(mask >> i & 1){
                                sum += b[i];
                        }
                }
                FOR(i, 0, n - 1){
                        if(sum == a[i]){
                                choose[i].push_back(mask);
                        }
                }
        }

        back_track(0, 0);
        cout << "NO";
}

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