Submission #927322

#TimeUsernameProblemLanguageResultExecution timeMemory
927322Art_ogoBank (IZhO14_bank)C++17
46 / 100
65 ms2652 KiB
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

#define int long long 
#define ll long long
#define fi first
#define se second
#define ve vector

using namespace std;

typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) x.begin(), x.end()

const int MAXN = 20;

bool dp[MAXN][1 << MAXN];
int a[MAXN], b[MAXN];

signed main(){
    int n, m;
    cin >> m >> n; 
    for(int i = 0; i < m; i++)
        cin >> b[i];
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < (1 << n); i++){
        int sum = 0;
        for(int j = 0; j < n; j++)
            if((i >> j) & 1){
                sum += a[j];
                dp[0][i] |= dp[0][i ^ (1 << j)];
            }
        if(sum == b[0])
            dp[0][i] = 1;
    }
    for(int it = 1; it < m; it++){
        for(int i = 0; i < (1 << n); i++){
            int sum = 0;
            for(int j = 0; j < n; j++)
                if((i >> j) & 1){
                    sum += a[j];
                    dp[it][i] |= dp[it][i ^ (1 << j)];
                }
            if(sum == b[it]){
                dp[it][i] = dp[it - 1][((1 << n) - 1) ^ i];
            }
        }
    }
    if(dp[m - 1][(1 << n) - 1])
        cout << "YES\n";
    else cout << "NO\n";
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...