Submission #886750

#	Time	Username	Problem	Language	Result	Execution time	Memory
886750		TahirAliyev	Bank (IZhO14_bank)	C++17	100 / 100	465 ms	173148 KiB

bank

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define oo 1e9
#define pb push_back

const int MAX = 21;

int n, m;
int a[MAX], b[MAX];

vector<int> ways[MAX];

int dp[MAX][(1 << MAX)];

bool rec(int mask, int i){
    if(i == n + 1) return 1;
    if(dp[i][mask] != -1) return dp[i][mask];
    bool ans = 0;
    for(int w : ways[i]){
        if((mask & w) == w){
            ans |= rec(mask ^ w, i + 1);
        }
    }
    return dp[i][mask] = ans;
}

int main(){
    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    for(int mask = 0; mask < (1 << m); mask++){
        int sum = 0;
        for(int i = 0; i < m; i++){
            if((1 << i) & mask) sum += b[i];
        }
        for(int i = 1; i <= n; i++){
            if(sum == a[i]){
                ways[i].push_back(mask);
            }
        }
    }
    if(rec((1 << m) - 1, 1)) cout << "YES\n";
    else cout << "NO\n";
}

Compilation message (stderr)

bank.cpp: In function 'bool rec(int, int)':
bank.cpp:28:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   28 |     return dp[i][mask] = ans;
      |            ~~~~~~~~~~~~^~~~~

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